2208: [Jsoi2010]连通数 - BZOJ

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

Description

Input

输入数据第一行是图顶点的数量，一个正整数N。接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。

Output

输出一行一个整数，表示该图的连通数。

Sample Input

010

001

100
Sample Output

9
HINT

对于100%的数据，N不超过2000。

看到这题然后马上打了一个tarjan

然后对每一个强连通分量dfs，A了之后感觉有点奇怪，这个复杂度是多少来着，我好像算不出来，果断百度题解

然后大囧。。。。。。怎么好像正解是tarjan+拓扑排序+状态压缩，只搜到了一个和我一样的做法

然后我想到这样做其实可以随随便便卡掉，还是n三方，于是又打了一遍正解，加个拓扑和状态压缩

  1 const
  2     maxn=200;
  3 var
  4     first,c,sum,dfn,low,z:array[0..maxn*2]of longint;
  5     next,last:array[0..maxn*maxn*2]of longint;
  6     flag:array[0..maxn*2]of boolean;
  7     f:array[0..maxn,0..maxn]of boolean;
  8     n,cnt,tot,ans,time,s:longint;
  9 
 10 procedure insert(x,y:longint);
 11 begin
 12     inc(tot);
 13     last[tot]:=y;
 14     next[tot]:=first[x];
 15     first[x]:=tot;
 16 end;
 17 
 18 procedure dfs(x:longint);
 19 var
 20     i:longint;
 21 begin
 22     inc(time);
 23     dfn[x]:=time;
 24     low[x]:=time;
 25     inc(s);
 26     z[s]:=x;
 27     flag[x]:=true;
 28     i:=first[x];
 29     while i<>0 do
 30       begin
 31         if dfn[last[i]]=0 then
 32           begin
 33             dfs(last[i]);
 34             if low[last[i]]<low[x] then low[x]:=low[last[i]];
 35           end
 36         else
 37           if flag[last[i]] and (low[last[i]]<low[x]) then low[x]:=low[last[i]];
 38         i:=next[i];
 39       end;
 40     if low[x]=dfn[x] then
 41     begin
 42       inc(cnt);
 43       while z[s+1]<>x do
 44         begin
 45           inc(sum[cnt]);
 46           c[z[s]]:=cnt;
 47           flag[z[s]]:=false;
 48           dec(s);
 49         end;
 50     end;
 51 end;
 52 
 53 procedure init;
 54 var
 55     i,j:longint;
 56     cc:char;
 57 begin
 58     readln(n);
 59     for i:=1 to n do
 60       begin
 61         for j:=1 to n do
 62           begin
 63             read(cc);
 64             if cc=‘1‘ then insert(i,j);
 65           end;
 66         readln;
 67       end;
 68     for i:=1 to n do
 69       if dfn[i]=0 then dfs(i);
 70     for i:=1 to n do
 71       begin
 72         j:=first[i];
 73         while j<>0 do
 74           begin
 75             if f[c[i],c[last[j]]]=false then
 76             begin
 77               insert(n+c[i],n+c[last[j]]);
 78               f[c[i],c[last[j]]]:=true;
 79             end;
 80             j:=next[j];
 81           end;
 82       end;
 83 end;
 84 
 85 function dfs2(x:longint):longint;
 86 var
 87     i:longint;
 88 begin
 89     dfs2:=sum[x-n];
 90     flag[x]:=true;
 91     i:=first[x];
 92     while i<>0 do
 93       begin
 94         if flag[last[i]]=false then inc(dfs2,dfs2(last[i]));
 95         i:=next[i];
 96       end;
 97 end;
 98 
 99 procedure work;
100 var
101     i,j:longint;
102 begin
103     for i:=1 to cnt do
104       begin
105         for j:=1 to cnt do
106           flag[j+n]:=false;
107         inc(ans,sum[i]*dfs2(i+n));
108       end;
109     writeln(ans);
110 end;
111 
112 begin
113     init;
114     work;
115 end.

View Code

  1 const
  2     maxn=2020;
  3 var
  4     first,c,sum,dfn,low,z,d:array[0..maxn*2]of longint;
  5     next,last:array[0..maxn*maxn*2]of longint;
  6     flag:array[0..maxn*2]of boolean;
  7     ff:array[0..maxn,0..maxn]of boolean;
  8     n,cnt,tot,ans,time,s:longint;
  9 
 10 procedure insert(x,y:longint);
 11 begin
 12     inc(tot);
 13     last[tot]:=y;
 14     next[tot]:=first[x];
 15     first[x]:=tot;
 16 end;
 17 
 18 procedure dfs(x:longint);
 19 var
 20     i:longint;
 21 begin
 22     inc(time);
 23     dfn[x]:=time;
 24     low[x]:=time;
 25     inc(s);
 26     z[s]:=x;
 27     flag[x]:=true;
 28     i:=first[x];
 29     while i<>0 do
 30       begin
 31         if dfn[last[i]]=0 then
 32           begin
 33             dfs(last[i]);
 34             if low[last[i]]<low[x] then low[x]:=low[last[i]];
 35           end
 36         else
 37           if flag[last[i]] and (low[last[i]]<low[x]) then low[x]:=low[last[i]];
 38         i:=next[i];
 39       end;
 40     if low[x]=dfn[x] then
 41     begin
 42       inc(cnt);
 43       while z[s+1]<>x do
 44         begin
 45           inc(sum[cnt]);
 46           c[z[s]]:=cnt;
 47           flag[z[s]]:=false;
 48           dec(s);
 49         end;
 50     end;
 51 end;
 52 
 53 procedure init;
 54 var
 55     i,j:longint;
 56     cc:char;
 57 begin
 58     readln(n);
 59     for i:=1 to n do
 60       begin
 61         for j:=1 to n do
 62           begin
 63             read(cc);
 64             if cc=‘1‘ then insert(i,j);
 65           end;
 66         readln;
 67       end;
 68     for i:=1 to n do
 69       if dfn[i]=0 then dfs(i);
 70     for i:=1 to n do
 71       begin
 72         j:=first[i];
 73         while j<>0 do
 74           begin
 75             if (ff[c[i],c[last[j]]]=false) and (c[i]<>c[last[j]]) then
 76             begin
 77               insert(n+c[i],n+c[last[j]]);
 78               inc(d[c[last[j]]]);
 79               ff[c[i],c[last[j]]]:=true;
 80             end;
 81             j:=next[j];
 82           end;
 83       end;
 84 end;
 85 
 86 var
 87     q:array[0..maxn]of longint;
 88     f:array[0..maxn,0..70]of longint;
 89     l,r:longint;
 90 
 91 procedure work;
 92 var
 93     i,j,k,tmp:longint;
 94 begin
 95     l:=1;
 96     r:=0;
 97     for i:=1 to cnt do
 98       if d[i]=0 then
 99       begin
100         inc(r);
101         q[r]:=i;
102       end;
103     while l<=r do
104       begin
105         j:=first[q[l]+n];
106         while j<>0 do
107           begin
108             dec(d[last[j]-n]);
109             if d[last[j]-n]=0 then
110             begin
111               inc(r);
112               q[r]:=last[j]-n;
113             end;
114             j:=next[j];
115           end;
116         inc(l);
117       end;
118     for i:=r downto 1 do
119       begin
120         f[q[i],q[i] div 30]:=1<<(q[i]mod 30);
121         j:=first[q[i]+n];
122         while j<>0 do
123           begin
124             for k:=0 to cnt div 30 do
125               f[q[i],k]:=f[q[i],k]or f[last[j]-n,k];
126             j:=next[j];
127           end;
128       end;
129     for i:=1 to cnt do
130       begin
131         tmp:=0;
132         for j:=1 to cnt do
133           if f[i,j div 30] and (1<<(j mod 30))>0 then inc(tmp,sum[j]);
134         inc(ans,tmp*sum[i]);
135       end;
136     writeln(ans);
137 end;
138 
139 begin
140     init;
141     work;
142 end.