BZOJ2208 [JSOI2010]连通数

2014.12.23 16:41 Tue| 5 visits oi_2015| 2015_刷题日常| Text

Solution

好久没有写Tarjan强连通分量了。复习一下……

处理这道题显然要先用Tarjan求一边强连通分量。每一个强连通分量中的点可以到达的顶点数目相同。之后缩点、建图、拓扑排序、计算答案。

这道题需要表示每一个连通分量可以到达的所有顶点。这一操作可以使用bitset水过 >o<

今天刚刚知道set/bitset都可以直接用"&"取交集,"|"取并集。真是厉害的很……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 2005
#define M 8100000

int n,ans;
char str[N];
queue<int> q;
bitset<N> c[N];
int h[N],belong[N];

int head[N],next[M],to[M],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y;
    next[cnt]=head[x]; head[x]=cnt;
}

int heads[N],nexts[M],tos[M],scnt;
inline void adds(int x,int y)
{
    tos[++scnt]=y;
    nexts[scnt]=heads[x]; heads[x]=scnt;
}

bool ins[N];
stack<int> s;
int sum,tot,low[N],deep[N],num[N];
void tarjan(int x)
{
    s.push(x); ins[x]=true;
    deep[x]=low[x]=++tot;
    for(int y,i=head[x];i;i=next[i])
        if(!deep[y=to[i]]) tarjan(y), low[x]=min(low[x],low[y]);
        else if(ins[y]) low[x]=min(low[x],deep[y]);
    if(low[x]==deep[x])
    {
        int t; sum++;
        do{
            t=s.top(); s.pop();
            ins[t]=false; belong[t]=sum;
            num[sum]++;
        }while(t!=x);
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str+1);
        for(int j=1;j<=n;j++)
            if(str[j]=='1') add(i,j);
    }
    for(int i=1;i<=n;i++)
        if(!deep[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
    {
        c[belong[i]].set(i);
        for(int y,j=head[i];j;j=next[j])
            if(belong[i]!=belong[y=to[j]])
                adds(belong[y],belong[i]), h[belong[i]]++;
    }
    for(int i=1;i<=sum;i++)
        if(!h[i])
            q.push(i);
    while(!q.empty())
    {
        int x=q.front(); q.pop();
        for(int y,i=heads[x];i;i=nexts[i])
        {
            h[y=tos[i]]--, c[y]|=c[x];
            if(h[y]==0) q.push(y);
        }
    }
    for(int i=1;i<=sum;i++)
        ans+=c[i].count()*num[i];
    cout<<ans<<endl;
}