2208: [Jsoi2010]连通数

题目链接

题目大意：求无向图中可达点对数

题解：直接 n2$n^2$dfs能过……
使用bitset优化传递闭包，直接floyed是
求出scc，缩点，在DAG上不断或运算是

我的收获：bitset强啊……

SCC

#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <algorithm>
using namespace std;
#define M 2010

int n,t,ans,head[M];
int tim,scnt,top;
int dfn[M],low[M],stk[M],col[M],sz[M];
bool ins[M];
char s[M];
bitset<M> num[M];

struct edge{int to,nex;}e[M*M];

void add(int u,int v){e[t].to=v,e[t].nex=head[u],head[u]=t++;}

void tarjan(int x){
    int now=0;
    dfn[x]=low[x]=++tim;
    stk[++top]=x;ins[x]=1;
    for(int i=head[x];i!=-1;i=e[i].nex){
        int v=e[i].to;
        if(!dfn[v]){tarjan(v);if(low[v]<low[x]) low[x]=low[v];}
        else if(ins[v]&&dfn[v]<low[x]) low[x]=dfn[v];
    }
    if(low[x]==dfn[x]){
        scnt++;
        while(x!=now){
            now=stk[top--];
            ins[now]=0;col[now]=scnt;++sz[scnt];
        }
    }
}

void work()
{
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        num[col[i]][i] = true;
    for(int i=1;i<=scnt;i++){
        ans+=sz[i]*sz[i];
        bitset<M> temp;
        for(int x=1;x<=n;x++)
            if(col[x]==i)
                for(int j=head[x];j!=-1;j=e[j].nex)
                    if(col[e[j].to]!=i)
                        temp|=num[col[e[j].to]];
        ans+=sz[i]*temp.count();
        num[i]|=temp;
    }
    cout<<ans<<endl;
}

void init()
{
    t=0;memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)
            if(s[j]=='1') add(i,j);
    }
}

int main()
{
    init();
    work();
    return 0;
}

floyed

#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
#define M 2000

int n,ans=0;
char s[M+5];
bitset<M+5> b[M+5];

void work()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            if(b[i][k]) b[i]|=b[k];
    for(int i=1;i<=n;i++) ans+=b[i].count();
    cout<<ans;
}

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)
            b[i][j]=(s[j]=='1'||i==j)?1:0;    
    }
}

int main()
{
    init();
    work();
    return 0;
}