思路
强连通分量的好题
对于每个博物馆，因为时间的限制条件，不好直接统计， 发现d很小，可以建出d层分层图，原图<u,v>的边变成<u,i>到<v,i+1>的边，<u,n>变成<v,1>的边，然后跑SCC，拆出每个点权值就是这个点这个时间有无贡献，此时一个强连通分量全选就能获得最大的价值了，然后注意同一个i只会出现在一个SCC中且只能被统计一次，所以要去下重代码
#include#include #include #include #include #include using namespace std;int cnt,v[5000100],fir[5000100],nxt[5000100],dfn[5000100],dfs_clock,low[5000100],sccno[5000100],vis[5000100],scccnt,sccnum[5000100],d,n,m;set scc_S[5000100];stack S;bitset<100100> mat[51];inline void addedge(int ui,int vi){ // printf("add:%d -> %d\n",ui,vi); ++cnt; v[cnt]=vi; nxt[cnt]=fir[ui]; fir[ui]=cnt;}int cnt2,v2[5000100],fir2[5000100],nxt2[5000100];inline void addedge2(int ui,int vi){ // printf("add2:%d -> %d\n",ui,vi); ++cnt2; v2[cnt2]=vi; nxt2[cnt2]=fir2[ui]; fir2[ui]=cnt2;}inline void tarjan(int u){ dfn[u]=low[u]=++dfs_clock; vis[u]=true; S.push(u); for(int i=fir[u];i;i=nxt[i]){ if(!dfn[v[i]]){ tarjan(v[i]); low[u]=min(low[u],low[v[i]]); } else if(vis[v[i]]){ low[u]=min(low[u],low[v[i]]); } } if(low[u]==dfn[u]){ ++scccnt; while(1){ int x=S.top(); S.pop(); vis[x]=false; sccno[x]=scccnt; if(x==u) break; } }}inline void sd(void){ for(int i=1;i<=d*n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=d;i++) for(int j=1;j<=n;j++){ if(mat[i][j]) scc_S[sccno[j+(i-1)*n]].insert(j); for(int k=fir[j+(i-1)*n];k;k=nxt[k]) if(sccno[j+(i-1)*n]!=sccno[v[k]]) addedge2(sccno[j+(i-1)*n],sccno[v[k]]); } for(int i=1;i<=scccnt;i++) sccnum[i]=scc_S[i].size();}int dp[5000100];bitset<5000100> visx;inline int dfs(int o){ // printf("u=%d\n",o); if(visx[o]) return dp[o]; visx[o]=true; for(int i=fir2[o];i;i=nxt2[i]){ dp[o]=max(dfs(v2[i]),dp[o]); } dp[o]+=sccnum[o]; return dp[o];}int main(){ scanf("%d %d %d",&n,&m,&d); for(int i=1;i<=m;i++){ int a,b; scanf("%d %d",&a,&b); for(int j=1;j