bzoj2208: [Jsoi2010]连通数 缩点+拓扑+状压

#include<bits/stdc++.h>
using namespace std;
#define N 2010
struct edge{
	edge* s;
	int v;
}e[N*N*2],*back=e,*h[N];
int low[N],num[N],scc[N],size[N];
int now;
void tarjan(int u){
	static int cnt;
	static stack<int> s;
	low[u]=num[u]=++cnt;
	s.push(u);
	for(edge* i=h[u];i;i=i->s)
		if(!num[i->v]){
			tarjan(i->v);
			low[u]=min(low[u],low[i->v]);
		}else if(!scc[i->v])
			low[u]=min(low[u],num[i->v]);
	if(low[u]==num[u]){
		static int v;
		++now;
		do{
			v=s.top();
			s.pop();
			++size[scc[v]=now];
		}while(u!=v);
	}
}
int main(){
	static char s[N+1];
	int n;
	scanf("%d",&n);
	for(int i=0;i!=n;++i){
		scanf("%s",s);
		for(int j=0;j!=n;++j)
			if(s[j]^48)
				h[i]=&(*back++=(edge){h[i],j});
	}
	for(int i=0;i!=n;++i)
		if(!num[i])
			tarjan(i);
	static bool v[N][N];
	for(int u=0;u!=n;++u)
		for(edge* i=h[u];i;i=i->s)
			v[scc[u]][scc[i->v]]=1;
	memset(h,0,sizeof h);
	static int in[N];
	for(int i=1;i<=now;++i)
		for(int j=1;j<=now;++j)
			if(i!=j&&v[i][j]){
				++in[j];
				h[i]=&(*back++=(edge){h[i],j});
			}
	static bitset<N> f[N];
	queue<int> q;
	for(int i=1;i<=now;++i){
		f[i][i]=1;
		if(!in[i])
			q.push(i);
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(edge* i=h[u];i;i=i->s){
			if(!--in[i->v])
				q.push(i->v);
			f[i->v]|=f[u];
		}
	}
	int ans=0;
	for(int i=1;i<=now;++i)
		for(int j=1;j<=now;++j)
			if(f[i][j])
				ans+=size[i]*size[j];
	printf("%d\n",ans);
}