2208: [Jsoi2010]连通数

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

2208: [Jsoi2010]连通数

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1371 Solved: 557
[Submit][Status]

Description

技术分享

Input

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

Output

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

Sample Input

3
010
001
100

Sample Output

HINT

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

Source

第一轮

题解：首先缩点，然后按照惯例重新构图，然后居然每个点都跑一边DFS求联通个数就AC了？？？（HansBug：逗我？！ wnjxyk：QAQ）然后上网刷题解才发现应该是tarjan重构图+拓排+状压DP。。。

  1 {$M 1000000000,0,maxlongint} //为了保险加了个这个^_^,唉Pascal里面栈空间是硬伤啊TT
  2 type
  3     point=^node;
  4     node=record
  5                g:longint;
  6                next:point;
  7     end;
  8     map=array[0..10000] of point;
  9 var
 10    i,j,k,l,m,n,h,t,ans:longint;
 11    a,c:map;
 12    d,e,g,b,f,low,dfn:array[0..100000] of longint;
 13    ss,s:array[0..100000] of boolean;
 14    p:point;
 15    c1:char;
 16 procedure add(var a:map;x,y:longint);
 17           var p:point;
 18           begin
 19                new(p);p^.g:=y;
 20                p^.next:=a[x];a[x]:=p;
 21           end;
 22 function min(x,y:longint):longint;
 23          begin
 24               if x<y then min:=x else min:=y;
 25          end;
 26 procedure tarjan(x:longint);
 27           var p:point;
 28           begin
 29                inc(h);low[x]:=h;dfn[x]:=h;
 30                inc(t);f[t]:=x;
 31                ss[x]:=true;s[x]:=true;
 32                p:=a[x];
 33                while p<>nil do
 34                      begin
 35                           if not(s[p^.g]) then
 36                              begin
 37                                   tarjan(p^.g);
 38                                   low[x]:=min(low[x],low[p^.g]);
 39                              end
 40                           else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]);
 41                           p:=p^.next;
 42                      end;
 43                if low[x]=dfn[x] then
 44                   begin
 45                        inc(ans);
 46                        while f[t+1]<>x do
 47                              begin
 48                                   b[f[t]]:=ans;
 49                                   ss[f[t]]:=false;
 50                                   dec(t);
 51                              end;
 52                   end;
 53           end;
 54 procedure dfs(x:longint);
 55           var p:point;
 56          begin
 57               p:=c[x];
 58               f[x]:=i;
 59               inc(m,d[x]);
 60               while p<>nil do
 61                     begin
 62                          if f[p^.g]<>i then dfs(p^.g);
 63                          p:=p^.next;
 64                     end;
 65          end;
 66 
 67 begin
 68      readln(n);
 69      for i:=1 to n do a[i]:=nil;
 70      for i:=1 to n do
 71          begin
 72               for j:=1 to n do
 73                   begin
 74                        read(c1);
 75                        if c1=‘1‘ then add(a,i,j);
 76                   end;
 77               readln;
 78          end;
 79      fillchar(b,sizeof(b),0);
 80      fillchar(f,sizeof(f),0);
 81      fillchar(s,sizeof(s),false);
 82      fillchar(ss,sizeof(ss),false);
 83      fillchar(low,sizeof(low),0);
 84      fillchar(dfn,sizeof(dfn),0);
 85      h:=0;t:=0;ans:=0;
 86      for i:=1 to n do if b[i]=0 then tarjan(i);
 87      fillchar(f,sizeof(f),0);
 88      fillchar(d,sizeof(d),0);
 89      fillchar(e,sizeof(e),0);
 90      for i:=1 to n do inc(d[b[i]]);
 91      for i:=1 to ans do c[i]:=nil;
 92      for i:=1 to n do
 93          begin
 94               p:=a[i];
 95               while p<>nil do
 96                     begin
 97                          if b[i]<>b[p^.g] then
 98                             begin
 99                                  inc(e[b[p^.g]]);
100                                  add(c,b[i],b[p^.g]);
101                             end;
102                          p:=p^.next;
103                     end;
104          end;
105      fillchar(f,sizeof(f),0);
106      n:=0;
107      for i:=1 to ans do
108          begin
109               m:=0;dfs(i);
110               n:=n+d[i]*m;
111          end;
112      writeln(n);
113      readln;
114 end.
115

接下来引用神犇们的正解

题目大意：给定一个n个点的有向图，求有多少点对(x,y),使x沿边可到达y

设f[i][j]为从i到j是否可达

首先强联通分量中的任意两个点均可达于是我们利用Tarjan缩点

缩点之后是一个拓扑图，我们求出拓扑序，沿着拓扑序从后向前DP，状态转移方程为：

f[i][k]=or{ f[j][k] } (i有直连边到达j,1<=k<=n,n为强连通分量的个数)

鉴于每个点的值只会是1或者0，所以我们可以直接状压，或者干脆开bitset，整体取或即可

时间复杂度O(mn/32)

今天各种手滑。。。Tarjan不赋值dpt和low，拓扑序求出来不用，各种调用错数组。。。终于彻底脑残了好开心233 QAQ

#include<bitset> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 2014 using namespace std; int n,ans,map[M][M],topo_map[M][M]; int dpt[M],low[M],v[M],cnt,belong[M],siz[M],_n,stack[M],top; int into[M],q[M],r,h; bitset<M>f[M]; void Tarjan(int x) { int y; dpt[x]=low[x]=++cnt; stack[++top]=x; for(y=1;y<=n;y++) if(map[x][y]) { if(v[y]) continue; if(dpt[y]) low[x]=min(low[x],dpt[y]); else Tarjan(y),low[x]=min(low[x],low[y]); } if(dpt[x]==low[x]) { int t; ++_n; do{ t=stack[top--]; belong[t]=_n; v[t]=1; ++siz[_n]; }while(t!=x); } } void Topology_Sort() { int i,y; for(i=1;i<=_n;i++) if(!into[i]) q[++r]=i; while(r!=h) { int x=q[++h]; for(y=1;y<=_n;y++) if(topo_map[x][y]) { into[y]--; if(!into[y]) q[++r]=y; } } } int main() { int i,j,x; cin>>n; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%1d",&map[i][j]); for(i=1;i<=n;i++) if(!v[i]) Tarjan(i); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]&&belong[i]!=belong[j]) { if(!topo_map[belong[i]][belong[j]]) into[belong[j]]++; topo_map[belong[i]][belong[j]]=1; f[belong[i]][belong[j]]=1; } for(i=1;i<=_n;i++) f[i][i]=1; Topology_Sort(); for(i=_n;i;i--) { x=q[i]; for(j=1;j<=_n;j++) if(topo_map[x][j]) f[x]|=f[j]; } for(i=1;i<=_n;i++) for(j=1;j<=_n;j++) if(f[i][j]) ans+=siz[i]*siz[j]; cout<<ans<<endl; }