题解 P4306 【[JSOI2010]连通数】

· · 题解

感谢zjq大佬（最楼下那位）给蒟蒻耐心的讲解（因为数组开小，满屏的花花绿绿还有TLE）

两种方法。第一种，就像是楼下所说，先tarjan+缩点，然后在新的图上建一个反向图，同时用拓扑排序不断更新每一个强连通分量能够到达的其他强连通分量。最后枚举每一个强连通分量，若h[i][j]为1则ans加上两个强连通分量的点数之积

上代码,具体看注解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#define fu(a,b,c) for(int a=b;a<=c;a++)
#define fd(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
const int N=2050,M=4000500;
int ver[M],Next[M],head[N];
int vc[M],nc[M],hc[N],low[N],dfn[N],stack[N],c[N],k[N],t[N];
bitset<N> h[N];
bool v[N];
int n,m,tot,num,cnt,tc,top,ans;
inline void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
inline void add_c(int x,int y)
{
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
void tarjan(int x)//跑一边tarjan
{
    low[x]=dfn[x]=++num;
    stack[++top]=x,v[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int y;
        cnt++;
        do{
            y=stack[top--];v[y]=0;
            c[y]=cnt;
            k[cnt]++;
        }while(x!=y);
        h[cnt][cnt]=1;
        //每一个强连通分量一定能够到达自己
    }
}
void solve()
{
//跑一边拓扑排序
    queue<int> q;
    fu(i,1,cnt)
    if(!t[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=hc[x];i;i=nc[i])
        {
            int y=vc[i];
            h[y]|=h[x];
            t[y]--;
            if(!t[y]) q.push(y);
        }
    }
}
int main()
{
    cin>>n;
    fu(i,1,n)
    {
        string s;
        cin>>s;
        fu(j,0,s.size()-1)
        if(s[j]=='1') add(i,j+1);
    }
    fu(i,1,n)
    if(!dfn[i]) tarjan(i);
    fu(x,1,n)
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(c[x]!=c[y]) add_c(c[y],c[x]),t[c[x]]++;
        //缩点，记得要建的是反向图，同时记录点的入度
    }
    solve();
    fu(i,1,cnt)
    fu(j,1,cnt)
    if(h[i][j]) ans+=k[i]*k[j];
    printf("%d",ans);
    return 0;
}

第二种方法。因为每一个整数有32位，我们设T=30，可以把n个点分为n/T组，每一组有至多30个点，每个点位于第i/30组的第i%30位

一个整数，可以表示为二进制，我们可以用此方法来表示一个点能否到达另一个点。比方说h[i]=100110（二进制），表示这一个点能够到达点1,2,4

我们用h[i][j/30]表示每一个强连通分量能否到达每一个点的情况。

if(h[i][j/30]&1<<(j%30)) ans+=k[i];

其中i代表强联通分量的编号，j代表点的编号，k[i]代表此强连通分量中共有多少个点。

如果一个强联通分量能够到达一个点，那么答案就累加上它的点数

剩下的，就是tarjan缩点再建反图拓扑，第一种方法中已说明，不再赘述

具体细节看注解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define fu(a,b,c) for(int a=b;a<=c;a++)
#define fd(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
const int N=2050,M=4000500,T=30;
int ver[M],Next[M],head[N];
int vc[M],nc[M],hc[N],low[N],dfn[N],stack[N],c[N],k[N],t[N];
int h[N][N/T];
bool v[N];
int n,m,tot,num,cnt,tc,top,ans;
inline void add(int x,int y)
{
    ver[++tot]=y,Next[tot]=head[x],head[x]=tot;
}
inline void add_c(int x,int y)
{
    vc[++tc]=y,nc[tc]=hc[x],hc[x]=tc;
}
void tarjan(int x)
{
    low[x]=dfn[x]=++num;
    stack[++top]=x,v[x]=1;
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(v[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        int y;
        cnt++;
        do{
            y=stack[top--];v[y]=0;
            c[y]=cnt;
            k[cnt]++;
            h[cnt][y/T]|=1<<(y%T);
            //一个强连通分量能够到达哪些点，记录
        }while(x!=y);
    }
}
void solve()
{
    queue<int> q;
    fu(i,1,cnt)
    if(!t[i]) q.push(i);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=hc[x];i;i=nc[i])
        {
            int y=vc[i];
            fu(j,0,n/T)
            h[y][j]|=h[x][j];
            t[y]--;
            if(!t[y]) q.push(y);
        }
    }
}
int main()
{
    cin>>n;
    fu(i,1,n)
    {
        string s;
        cin>>s;
        fu(j,0,n-1)
        if(s[j]=='1') add(i,j+1);
    }
    fu(i,1,n)
    if(!dfn[i]) tarjan(i);
    fu(x,1,n)
    for(int i=head[x];i;i=Next[i])
    {
        int y=ver[i];
        if(c[x]!=c[y]) add_c(c[y],c[x]),t[c[x]]++;
    }
    solve();
    fu(i,1,n)
    {
        int l=i/T,r=1<<(i%T);
        fu(j,1,cnt)
        if(h[j][l]&r) ans+=k[j];
        //判断每一个强连通分量能否到达某个点
    }
    printf("%d",ans);
    return 0;
}