swift's blog

swift's blog

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

posted on 2019-07-29 12:05:32 | under 题解 |

排版哪里有问题啊QAQ

根据题意,一个强连通分量一定是半联通子图,所以多个强联通分量也一定是半联通子图,所以问题就转化成了在一个缩点后的图上找最长链,步骤如下:

1.缩点

先用tarjan记录每一个强联通分量的大小和每个点在哪个强连通分量里

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]++;
    }
}

如果有两个有边连接的点不在一个强连通分量里,那么这两个强连通分量之间就有边,我这里直接把缩点后的图新建在另一个前向星里了,注意要去重,即不能在两个强连通分量间建多条边。

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,最后找最大值即可

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]);
            }
        }
    }

完整代码:

#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;
}