poj3177 Redundant Paths【tarjan】
题目点击这里
题目简要翻译：
有F个牧场，R条道路，形如<A, B>，表示牧场A到牧场B有一条通路（双向的），给出路保证每两个牧场都有通路，有些cow每次都得走同样的路有A到B。
问：再建最少的路使得任意两个牧场间都有两条不同的路，不同，指的是由A到B的过程中没有经过任一同一段路。
小小吐槽：
其实呢，这题去年年底就在poj上A掉了，但是在我们学校的oj出了问题，就是在存边的方式上（我能说是因为我不会写邻接表然后写邻接矩阵就爆空间了吗），我们学校的oj内存限制32MB。。。
然后最近突然想起这题还留了个坑，然后翻出来以前的代码改成了邻接表型，结果WA了，上网一查发现这题有重边（同一条边会输入两次但是只算一条边），邻接矩阵默认认为是两条互相独立的边然后缩点时就出了点小小的问题，加了个重边判断就可以了。
接下来就是题目解法：
题目首先要求任意两点有两条不同的道路连接，显然就是要在原图上加边使其形成一个双连通图，关于双连通图有一个不错的文章，这里就当作各位已经知道了双连通、割点还有桥的定义。
原图不一定是双连通图，那么就先将原图的双连通分量缩点，形成一个新的图，首先新图肯定是个森林，对于森林里的每棵树，两个点之间已经有了一条道路，而不属于同一棵树之间的点还没有道路连接，所以我们将一棵树拿出来，连一条由度数为1节点到其他树度数为1节点的边（没有其他树的度数为1节点就用自己树的度数为1节点代替），重复这个过程即可，那么显然新图就是一个双连通图，我们的答案就是缩点后度数为1节点的数量÷2（向上取整）。
证明证明证明：
刚才的构造完毕后，整个图一定是连通图，那么如何证明这个图是双连通图呢？考虑每一个节点，如果原来的度数不为1，就可以从自己的父亲出发到另一个点，也可以从自己的儿子出发到那个点，因为原来的叶子节点一定有连到其他树的边，如果原来的度数为1，也是同样的理由。
代码:
var v,next:array[1..30000]of longint; low,dfn,du,a:array[1..5000]of longint; b:array[1..5000]of boolean; n,m,i,j,k,p,q:longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure dfs(u,p:longint); var i:longint; begin b[u]:=true; inc(k); dfn[u]:=k; low[u]:=k; i:=a[u]; while i<>0 do begin if not b[v[i]] then begin dfs(v[i],u); low[u]:=min(low[u],low[v[i]]); end; if b[v[i]] and (v[i]<>p) then low[u]:=min(low[u],dfn[v[i]]); i:=next[i]; end; end; procedure adde(uu,vv:longint); var i:longint; begin i:=a[uu]; while i<>0 do begin if v[i]=vv then exit; i:=next[i]; end; inc(k); v[k]:=vv; next[k]:=a[uu]; a[uu]:=k; inc(k); v[k]:=uu; next[k]:=a[vv]; a[vv]:=k; end; begin read(n,m); k:=0; for i:=1 to m do begin read(p,q); adde(p,q); end; fillchar(b,sizeof(b),false); k:=0; dfs(1,1); for i:=1 to n do begin j:=a[i]; while j<>0 do begin if low[i]<>low[v[j]] then inc(du[low[v[j]]]); j:=next[j]; end; end; k:=0; for i:=1 to n do if du[i]=1 then inc(k); writeln((k+1) div 2); end.
发表回复