[bzoj 2208] 연통 수 tarjan 축 점 & 상 압 상수 최적화

이 문 제 는 O (N ^ 3) 보다 빠 른 알고리즘 이 없다 고 생각 합 니 다.나무의 분 치 를 시작 하지 않 으 면?
       우선 tarjan 축 점 (분명), 그 다음 에 DAG 입 니 다.그 다음 에 축 소 된 강 한 연결 분량 에 가중치 가 함 유 된 점 의 개 수 를 주 고 강 한 연결 분량 에 대한 답 은 이 강 한 연결 분량 의 가중치 에 이 강 한 연결 분량 이 도달 할 수 있 는 점 의 개수 (자신 포함) 를 곱 하 는 것 이다.f [i] 로 강 한 연결 분량 i 가 도착 할 수 있 는 점 의 집합 을 나타 낸다 고 가정 하면 f [i] | = {f [j]} 이 존재 하 는 변 (u, v) 으로 u 가 강 한 연결 분량 i 에 있 고 v 가 j 에 있 으 면 이것 은 기억 화 로 쉽게 해결 할 수 있다 (전달 해도 된다).
       바 이 너 리 로 표시 하면 폭발 (2 ^ n) 이 분명 하기 때문에 이 바 이 너 리 를 n / 30 개의 바 이 너 리 로 바 꾸 면 각 수의 크기 는 2 ^ 30 밖 에 안 됩 니 다.f 배열 의 시간 복잡 도 는 O (N + M) N / 30) = O (N ^ 3) 이지 만 n 이 최대 2000 이 고 1 / 30 이라는 아주 작은 상수 가 있 는 것 을 감안 하면 실제 운행 속 도 는 매우 빠르다.
AC 코드 는 다음 과 같 습 니 다.

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 2005
using namespace std;

int n,m,cnt,tp,tmp,dfsclk,s[N],pos[N],low[N],scc[N],sum[N],f[N][105];
int tot,fst[N],pnt[N*N],nxt[N*N]; bool vis[N],a[N][N];
void dfs(int x){
	s[++tp]=x; pos[x]=low[x]=++dfsclk; int i;
	for (i=1; i<=n; i++) if (a[x][i]){
		if (!pos[i]){ dfs(i); low[x]=min(low[x],low[i]); } else
		if (!scc[i]) low[x]=min(low[x],pos[i]);
	}
	if (low[x]==pos[x]){		
		for (sum[++cnt]=1; s[tp]!=x; tp--){
			scc[s[tp]]=cnt; sum[cnt]++;
		}
		scc[x]=cnt; tp--;
	}
}
void add(int aa,int bb){
	pnt[++tot]=bb; nxt[tot]=fst[aa]; fst[aa]=tot;
}
void solve(int x){
	if (vis[x]) return; vis[x]=1; int p,i;
	for (p=fst[x]; p; p=nxt[p]){
		int y=pnt[p]; solve(y);
		for (i=0; i<=m; i++) f[x][i]|=f[y][i];
	}
}
int work(int x){
	int ans=0; for (; x; x-=x&(-x)) ans++; return ans;
}
int main(){
	scanf("%d",&n); int i,j;
	for (i=1; i<=n; i++){
		char ch=getchar(); while (ch<'0' || ch>'1') ch=getchar();
		for (j=1; j<=n; j++){
			a[i][j]=(ch=='1'); ch=getchar();
		}
	}
	for (i=1; i<=n; i++) if (!pos[i]) dfs(i);
	int ans=0; m=n/30;
	for (i=1; i<=n; i++) f[scc[i]][i/30]|=1<<(i%30);
	for (i=1; i<=n; i++)
		for (j=1; j<=n; j++) if (a[i][j] && scc[i]!=scc[j]) add(scc[i],scc[j]);
	for (i=1; i<=cnt; i++) if (!vis[i]){
		solve(i); for (j=0; j<=m; j++) ans+=sum[i]*work(f[i][j]);	
	}
	printf("%d
",ans);
	return 0;
}

by lych
2016.1.27