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
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[..] of point;
var
i,j,k,l,m,n,h,t,ans:longint;
a,c:map;
d,e,g,b,f,low,dfn:array[..] of longint;
ss,s:array[..] 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+]<>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:= to n do a[i]:=nil;
for i:= to n do
begin
for j:= to n do
begin
read(c1);
if c1='' then add(a,i,j);
end;
readln;
end;
fillchar(b,sizeof(b),);
fillchar(f,sizeof(f),);
fillchar(s,sizeof(s),false);
fillchar(ss,sizeof(ss),false);
fillchar(low,sizeof(low),);
fillchar(dfn,sizeof(dfn),);
h:=;t:=;ans:=;
for i:= to n do if b[i]= then tarjan(i);
fillchar(f,sizeof(f),);
fillchar(d,sizeof(d),);
fillchar(e,sizeof(e),);
for i:= to n do inc(d[b[i]]);
for i:= to ans do c[i]:=nil;
for i:= 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),);
n:=;
for i:= to ans do
begin
m:=;dfs(i);
n:=n+d[i]*m;
end;
writeln(n);
readln;
end.
接下来引用神犇们的正解