2208: [Jsoi2010]连通数

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

9

HINT

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

Source

第一轮

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

{$M 1000000000,0,maxlongint} //为了保险加了个这个^_^,唉Pascal里面栈空间是硬伤啊TT
type
    point=^node;
    node=record
               g:longint;
               next:point;
    end;
    map=array[0..10000] of point;
var
   i,j,k,l,m,n,h,t,ans:longint;
   a,c:map;
   d,e,g,b,f,low,dfn:array[0..100000] of longint;
   ss,s:array[0..100000] of boolean;
   p:point;
   c1:char;
procedure add(var a:map;x,y:longint);
          var p:point;
          begin
               new(p);p^.g:=y;
               p^.next:=a[x];a[x]:=p;
          end;
function min(x,y:longint):longint;
         begin
              if x<y then min:=x else min:=y;
         end;
procedure tarjan(x:longint);
          var p:point;
          begin
               inc(h);low[x]:=h;dfn[x]:=h;
               inc(t);f[t]:=x;
               ss[x]:=true;s[x]:=true;
               p:=a[x];
               while p<>nil do
                     begin
                          if not(s[p^.g]) then
                             begin
                                  tarjan(p^.g);
                                  low[x]:=min(low[x],low[p^.g]);
                             end
                          else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]);
                          p:=p^.next;
                     end;
               if low[x]=dfn[x] then
                  begin
                       inc(ans);
                       while f[t+1]<>x do
                             begin
                                  b[f[t]]:=ans;
                                  ss[f[t]]:=false;
                                  dec(t);
                             end;
                  end;
          end;
procedure dfs(x:longint);
          var p:point;
         begin
              p:=c[x];
              f[x]:=i;
              inc(m,d[x]);
              while p<>nil do
                    begin
                         if f[p^.g]<>i then dfs(p^.g);
                         p:=p^.next;
                    end;
         end;

begin
     readln(n);
     for i:=1 to n do a[i]:=nil;
     for i:=1 to n do
         begin
              for j:=1 to n do
                  begin
                       read(c1);
                       if c1='1' then add(a,i,j);
                  end;
              readln;
         end;
     fillchar(b,sizeof(b),0);
     fillchar(f,sizeof(f),0);
     fillchar(s,sizeof(s),false);
     fillchar(ss,sizeof(ss),false);
     fillchar(low,sizeof(low),0);
     fillchar(dfn,sizeof(dfn),0);
     h:=0;t:=0;ans:=0;
     for i:=1 to n do if b[i]=0 then tarjan(i);
     fillchar(f,sizeof(f),0);
     fillchar(d,sizeof(d),0);
     fillchar(e,sizeof(e),0);
     for i:=1 to n do inc(d[b[i]]);
     for i:=1 to ans do c[i]:=nil;
     for i:=1 to n do
         begin
              p:=a[i];
              while p<>nil do
                    begin
                         if b[i]<>b[p^.g] then
                            begin
                                 inc(e[b[p^.g]]);
                                 add(c,b[i],b[p^.g]);
                            end;
                         p:=p^.next;
                    end;
         end;
     fillchar(f,sizeof(f),0);
     n:=0;
     for i:=1 to ans do
         begin
              m:=0;dfs(i);
              n:=n+d[i]*m;
         end;
     writeln(n);
     readln;
end.
       

接下来引用神犇们的正解

 

题目大意：给定一个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; }