题解 P2272 【[ZJOI2007]最大半连通子图】

swiftc

2019-07-29 12:05:32

Solution

__排版哪里有问题啊QAQ__ 根据题意,一个强连通分量一定是半联通子图,所以多个强联通分量也一定是半联通子图,所以问题就转化成了在一个缩点后的图上找最长链,步骤如下: ### 1.缩点 先用tarjan记录每一个强联通分量的大小和每个点在哪个强连通分量里 ```cpp void tarjan(int now){ if(vis[now])return; dfn[now]=low[now]=++Time; tmp.push(now); vis[now]=1; for(int i=head[now];i;i=nxt[i]){ if(!dfn[to[i]]){ tarjan(to[i]); low[now]=min(low[now],low[to[i]]); }else if(vis[to[i]]){ low[now]=min(low[now],dfn[to[i]]); } } if(low[now]==dfn[now]){ _cnt++; while(tmp.top()!=now){ vis[tmp.top()]=0; in[tmp.top()]=_cnt; siz[_cnt]++; tmp.pop(); } tmp.pop(); vis[now]=0; in[now]=_cnt; siz[_cnt]++; } } ``` 如果有两个有边连接的点不在一个强连通分量里,那么这两个强连通分量之间就有边,我这里直接把缩点后的图新建在另一个前向星里了,注意要去重,即不能在两个强连通分量间建多条边。 ```cpp for(int i=1;i<=n;i++){ for(int j=head[i];j;j=nxt[j]){ if(in[i]!=in[to[j]]){ bool flag=0; for(int ii=_head[in[i]];ii;ii=_nxt[ii]){ if(_to[ii]==in[to[j]])flag=1; } if(flag)continue; _nxt[++__cnt]=_head[in[i]]; _head[in[i]]=__cnt; _to[__cnt]=in[to[j]]; du[in[to[j]]]++; } } } ``` ### 2.求最长链 最后用拓扑排序来DP求最长链:先把入度为0的强连通分量放入队列,每次取出第一个开始更新,```num[i]```表示以i为结尾的最长链有几个```ans[i]```表示最长链的长度,更新时如果可以让以这个点结尾的链变得更长,就把```num[i]```设为1,更新```ans[i]```,如果又发现一条和以这个点结尾最长链一样长的链,就把```num[i]+=1```,最后找最大值即可 ```cpp queue<int>q; for(int i=1;i<=_cnt;i++){ if(du[i]==0)q.push(i); ans[i]=siz[i]; num[i]=1; } while(!q.empty()){ int now=q.front(); q.pop(); for(int i=_head[now];i;i=_nxt[i]){ if(ans[_to[i]]<ans[now]+siz[_to[i]]){ ans[_to[i]]=ans[now]+siz[_to[i]]; num[_to[i]]=num[now]; } else if(ans[_to[i]]==ans[now]+siz[_to[i]]){ num[_to[i]]=(num[now]%x+num[_to[i]]%x)%x; } du[_to[i]]--; if(du[_to[i]]==0){ q.push(_to[i]); } } } ``` 完整代码: ```cpp #include<bits/stdc++.h> using namespace std; int du[3000001],head[3000001],nxt[3000001],to[3000001],dfn[3000001],low[3000001],vis[3000001],in[3000001],siz[3000001]; int n,m,x,cnt,Time,_cnt,__cnt; stack<int>tmp; void tarjan(int now){ if(vis[now])return; dfn[now]=low[now]=++Time; tmp.push(now); vis[now]=1; for(int i=head[now];i;i=nxt[i]){ if(!dfn[to[i]]){ tarjan(to[i]); low[now]=min(low[now],low[to[i]]); }else if(vis[to[i]]){ low[now]=min(low[now],dfn[to[i]]); } } if(low[now]==dfn[now]){ _cnt++; while(tmp.top()!=now){ vis[tmp.top()]=0; in[tmp.top()]=_cnt; siz[_cnt]++; tmp.pop(); } tmp.pop(); vis[now]=0; in[now]=_cnt; siz[_cnt]++; } } int _head[3000001],_nxt[3000001],_to[3000001],ans[3000001],num[3000001]; int maxn=-1,id; int main(){ scanf("%d%d%d",&n,&m,&x); for(int i=1;i<=m;i++){ int a,b; scanf("%d%d",&a,&b); nxt[++cnt]=head[a]; head[a]=cnt; to[cnt]=b; } for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ for(int j=head[i];j;j=nxt[j]){ if(in[i]!=in[to[j]]){ bool flag=0; for(int ii=_head[in[i]];ii;ii=_nxt[ii]){ if(_to[ii]==in[to[j]])flag=1; } if(flag)continue; _nxt[++__cnt]=_head[in[i]]; _head[in[i]]=__cnt; _to[__cnt]=in[to[j]]; du[in[to[j]]]++; } } } queue<int>q; for(int i=1;i<=_cnt;i++){ if(du[i]==0)q.push(i); ans[i]=siz[i]; num[i]=1; } while(!q.empty()){ int now=q.front(); q.pop(); for(int i=_head[now];i;i=_nxt[i]){ if(ans[_to[i]]<ans[now]+siz[_to[i]]){ ans[_to[i]]=ans[now]+siz[_to[i]]; num[_to[i]]=num[now]; } else if(ans[_to[i]]==ans[now]+siz[_to[i]]){ num[_to[i]]=(num[now]%x+num[_to[i]]%x)%x; } du[_to[i]]--; if(du[_to[i]]==0){ q.push(_to[i]); } } } int maxn1=-1,maxn2=-1; for(int i=1;i<=_cnt;i++){ if(ans[i]>maxn1){ maxn1=ans[i]; maxn2=num[i]; } else if(ans[i]==maxn1){ maxn2=(maxn2%x+num[i]%x)%x; } } printf("%d\n%d\n",maxn1,maxn2); return 0; } ```