2208: [Jsoi2010]连通数

对于原图建反图，考虑到有环，tarjan缩点，就得到一张有向无环图，用bitset记录能到某scc的点（原图点），跑拓扑将bitset或（|）下去就可以了，最后答案为∑（bitset中1的个数*scc的大小）。开始考虑错了：

 1 for(int i=1;i<=n;i++) 2 ans+=ll[belong[i]].count()+scc[belong[i]].size()-1; 
正确做法：

1 for(int i=1;i<=tot;i++)
2 ans+=ll[i].count()*scc[i].size();

View Code

#include<iostream>
#include<bitset>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
#define MAXN 2010
using namespace std;
struct node
{
    int u,v,nxt;
    #define u(x) ed[x].u
    #define v(x) ed[x].v
    #define n(x) ed[x].nxt
    #define u2(x) ed2[x].u
    #define v2(x) ed2[x].v
    #define n2(x) ed2[x].nxt
}ed[MAXN*MAXN],ed2[MAXN*MAXN];
int first[MAXN],num_e;
#define f(x) first[x]
int first2[MAXN],num_e2;
#define f2(x) first2[x]
int n;
inline void add(int u,int v)
{
    ++num_e;
    u(num_e)=u;
    v(num_e)=v;
    n(num_e)=f(u);
    f(u)=num_e;
}
inline void add2(int u,int v)
{
    ++num_e2;
    u2(num_e2)=u;
    v2(num_e2)=v;
    n2(num_e2)=f2(u);
    f2(u)=num_e2;
}
int dfn[MAXN],low[MAXN],belong[MAXN];
int stack[MAXN],top,cnt,tot;
bool v[MAXN];
vector<int> scc[MAXN];
void tarjan(int x)
{
    dfn[x]=++cnt;low[x]=cnt;
    stack[++top]=x;v[x]=1;
    for(int i=f(x);i;i=n(i))
        if(!dfn[v(i)])tarjan(v(i)),low[x]=min(low[x],low[v(i)]);
        else if(v[v(i)])low[x]=min(low[x],low[v(i)]);
    if(dfn[x]==low[x])
    {
        tot++;v[x]=0;
        while(stack[top]!=x)
        {
            belong[stack[top]]=tot;
            v[stack[top]]=0;
            scc[tot].push_back(stack[top--]);
        }
        belong[stack[top]]=tot;
        scc[tot].push_back(stack[top--]);
    }
}
int du[MAXN];
signed main()
{
    scanf("%lld",&n);
    char ch;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>ch;
            if(ch=='1')add(j,i);
        }
    for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=num_e;i++)
    if(belong[u(i)]!=belong[v(i)])
        add2(belong[u(i)],belong[v(i)]),du[belong[v(i)]]++;
    bitset<MAXN> ll[MAXN];
    queue<int>q;
    for(int i=1;i<=tot;i++)
        for(int j=0;j<scc[i].size();j++)
            ll[i][scc[i][j]]=1;
    for(int i=1;i<=tot;i++)
    if(!du[i])q.push(i);
    while(q.size())
    {
        int k=q.front();q.pop();
        for(int i=f2(k);i;i=n2(i))
        {
            ll[v2(i)]|=ll[k];
            du[v2(i)]--;
            if(!du[v2(i)])q.push(v2(i));
        }
    }
    int ans=0;
    for(int i=1;i<=tot;i++)
        ans+=ll[i].count()*scc[i].size();
    printf("%lld
",ans);
}

View Code