【BZOJ】【2208】【JSOI2010】连通数

浏览数：53 / 时间：2015年06月09日

题解：

　　1.Tarjan缩点以后对每个连通分量进行深搜，看能到哪些连通分量，能到达的所有连通分量的size之和记为sum。则第i个连通分量对答案的贡献为size[i]*sum（到其他连通分量）+size[i]*size[i]（本身互相可达）

　　2.在网上搜了一下……这题可以直接dfs过……汗。“正解”是Tarjan缩点+拓扑排序+状态压缩

  1 /**************************************************************
  2     Problem: 2208
  3     User: Tunix
  4     Language: C++
  5     Result: Accepted
  6     Time:9476 ms
  7     Memory:64772 kb
  8 ****************************************************************/
  9  
 10 //BZOJ 2208
 11 #include<vector>
 12 #include<cstdio>
 13 #include<cstdlib>
 14 #include<cstring>
 15 #include<iostream>
 16 #include<algorithm>
 17 #define rep(i,n) for(int i=0;i<n;++i)
 18 #define F(i,j,n) for(int i=j;i<=n;++i)
 19 #define D(i,j,n) for(int i=j;i>=n;--i)
 20 using namespace std;
 21 const int N=2015;
 22 typedef long long LL;
 23 void read(int &v){
 24     v=0; int sign=1; char ch=getchar();
 25     while(ch<‘0‘||ch>‘9‘) {if (ch==‘-‘) sign=-1; ch=getchar();}
 26     while(ch>=‘0‘&&ch<=‘9‘) {v=v*10+ch-‘0‘; ch=getchar();}
 27     v*=sign;
 28 }
 29 /*******************tamplate********************/
 30 int to1[N*N],head1[N],next1[N*N],cnt=0;
 31 int to2[N*N],head2[N],next2[N*N];
 32 void ins1(int x,int y){
 33     to1[++cnt]=y; next1[cnt]=head1[x]; head1[x]=cnt;
 34 }
 35 void ins2(int x,int y){
 36     to2[++cnt]=y; next2[cnt]=head2[x]; head2[x]=cnt;
 37 }
 38 /***********************************************/
 39 int n,m;
 40 int dfn[N],low[N],dfs_clock=0,belong[N],num,size[N];
 41 int st[N],top=0;
 42 bool in[N];
 43 void tarjan(int x){
 44     int y;
 45     dfn[x]=low[x]=++dfs_clock;
 46     st[top++]=x;
 47     in[x]=1;
 48     for(int i=head1[x];i;i=next1[i]){
 49         y=to1[i];
 50         if (!dfn[y]){
 51             tarjan(y);
 52             low[x]=min(low[x],low[y]);
 53         }
 54         else if (in[y]) low[x]=min(low[x],dfn[y]);
 55     }
 56     if (low[x]==dfn[x]){
 57         num++; size[num]=0;
 58         for(y=0;y!=x;){
 59             y=st[--top];
 60             in[y]=0;
 61             belong[y]=num;
 62             size[num]++;
 63         }
 64     }
 65 }
 66 void rebuild(){
 67     cnt=0;
 68     F(x,1,n)
 69         for(int i=head1[x];i;i=next1[i])
 70             if (belong[x]!=belong[to1[i]])
 71                 ins2(belong[x],belong[to1[i]]);
 72 }
 73 /***********************************************/
 74 bool vis[N];
 75 int sum=0;
 76 void dfs(int x){
 77     int y;
 78     for(int i=head2[x];i;i=next2[i]){
 79         y=to2[i];
 80         if (!vis[y]){
 81             vis[y]=1;
 82             sum+=size[y];
 83             dfs(y);
 84         }
 85     }
 86 }      
 87 void solve(){
 88     LL ans=0;
 89     F(i,1,num){
 90         memset(vis,0,sizeof vis);
 91         sum=0;
 92         dfs(i);
 93         ans+=size[i]*sum+size[i]*size[i];
 94     }
 95     printf("%lld\n",ans);
 96 }
 97 int main(){
 98     #ifndef ONLINE_JUDGE
 99     freopen("input.txt","r",stdin);
100     #endif
101     read(n);
102     char s[N];
103     F(i,1,n){
104         scanf("%s",s);
105         rep(j,strlen(s))
106             if (s[j]==‘1‘) ins1(i,j+1);
107     }
108     F(i,1,n) if (!dfn[i]) tarjan(i);
109     rebuild();
110     solve();
111     return 0;
112 }