# Bzoj2208 [jsoi2010]连通数

Posted by yjjr's blog on February 6, 2018

Description

Input

Output

Sample Input

3
010
001
100

Sample Output

9

HINT

Tarjan缩点重新构图

F[i][j]表示i和j点之间的联通情况，然后按照拓扑序从后往前整体取或，最后用每个联通块的大小来更新答案

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=2006;
int n,cnt=0,scc,top=0,tim,lim,ans=0;
int belong[maxn],hav[maxn],mark[maxn][maxn];
char ch[maxn];
struct edge{int to,next;}e[4000006],ed[4000006];
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define v e[i].to
#define newreg(x) for(int i=h[x];i;i=ed[i].next)
#define newv ed[i].to
void tarjan(int x)
{
int now=0;
dfn[x]=low[x]=++tim;que[++top]=x;inque[x]=1;
reg(x)
if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}
else if(inque[v])low[x]=min(low[x],dfn[v]);
if(low[x]==dfn[x]){
scc++;
while(now!=x){
now=que[top--];
inque[now]=0;belong[now]=scc;hav[scc]++;
}
}
}

void rebuild()
{
cnt=0;
rep(k,1,n)
reg(k)
if(belong[k]!=belong[v])ed[++cnt]=(edge){belong[k],h[belong[v]]},h[belong[v]]=cnt,r[belong[k]]++;
}
int main()
{
lim=n/30+1;
rep(i,1,n){
scanf("%s",ch);
rep(j,1,n)
}
rep(i,1,n)
if(!dfn[i])tarjan(i);
rebuild();
top=0;int now;
rep(i,1,n)mark[belong[i]][i/30+1]|=(1<<(i%30));
rep(i,1,scc)if(!r[i])que[++top]=i;
while(top){
now=que[top--];
newreg(now){
rep(j,1,lim)mark[newv][j]|=mark[now][j];
r[newv]--;
if(!r[newv])que[++top]=newv;
}
}
rep(i,1,scc)
rep(j,1,n)
if((mark[i][j/30+1])&(1<<(j%30)))ans+=hav[i];
cout<<ans<<endl;
return 0;
}