题解 P4306 【[JSOI2010]连通数】
YoungNeal
2018-06-02 22:02:04
## Solution
题解在博客[食用](https://www.cnblogs.com/YoungNeal/p/9127102.html)效果更佳哦~
~~下面题解都不是正解诶。。交到BZOJ上会WA到死~~
$Tarjan$ 缩点 $+$ 拓扑排序 $+$ $bitset$ 优化状压
显然对于每个强联通分量我们都要求出在新图上它能到达哪些点。
如何求呢？
法一： $dfs$，对于每个强联通分量找一下它连出去的边能到达哪些联通块，统计答案即可。~~(只是口胡一下没有写这种方法如果写不出来别找我)~~
法二：我们定义数组 $f[i][j]$ 表示能否从第 $i$ 个连通分量到达第 $j$ 个连通分量。因为值只能为 $0/1$，我们用 $bitset$ 来状压第二维。因为 $f[j]=or(f[i]),j\;can\;go\;to\;i$，所以我们在新图上建立一张反图，拓扑排序，按照拓扑序即可求出每个点能到达哪些点。复杂度 O(n^2/32)。
## Code
```cpp
#include<queue>
#include<bitset>
#include<cstdio>
#include<cctype>
#include<iostream>
#define N 2005
#define min(A,B) ((A)<(B)?(A):(B))
int ans;
char ch[N];
bool in[N];
int n,cnt,sum,tot;
int dfn[N],low[N];
std::bitset<N> f[N];
std::queue<int> topo;
int belong[N],deg[N];
int head[N],head2[N];
int stk[N],top,sze[N];
struct Edge{
int to,nxt;
}edge[N*N],edge2[N*N];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
void add2(int x,int y){
edge2[++cnt].to=y;
edge2[cnt].nxt=head2[x];
head2[x]=cnt;
}
int getint(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
void tarjan(int now){
dfn[now]=low[now]=++sum;
stk[++top]=now;in[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
tarjan(to);
low[now]=min(low[now],low[to]);
}
else if(in[to])
low[now]=min(low[now],dfn[to]);
}
if(low[now]==dfn[now]){
int y; tot++;
do{
y=stk[top--];
belong[y]=tot;
sze[tot]++;
in[y]=0;
}while(y!=now);
}
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",ch);
for(int j=0;j<n;j++){
if(ch[j]=='0') continue;
add(i,j+1);
}
}
cnt=0;
for(int i=1;i<=n;i++){
if(!dfn[i])
tarjan(i);
}
for(int x=1;x<=n;x++){
for(int i=head[x];i;i=edge[i].nxt){
int to=edge[i].to;
if(belong[x]==belong[to]) continue;
deg[belong[x]]++;
add2(belong[to],belong[x]);
}
}
for(int i=1;i<=tot;i++)
f[i][i]=1;
for(int i=1;i<=tot;i++){
if(!deg[i])
topo.push(i);
}
while(topo.size()){
int u=topo.front();topo.pop();
for(int i=head2[u];i;i=edge2[i].nxt){
int to=edge2[i].to;
deg[to]--;
f[to]|=f[u];
if(!deg[to])
topo.push(to);
}
}
for(int i=1;i<=tot;i++){
for(int j=1;j<=tot;j++){
if(f[i][j])
ans+=sze[i]*sze[j];
}
}
printf("%d\n",ans);
return 0;
}
```