题目描述：
这是道题题意有点迷（或者是我语文不好），但其实实际上求的就是图中连通块的个数，然后在连通块与连通块之间连边建图跑最小生成树。但是……这个图可能是不连通的……求桥的数量和总长
于是我立刻想到了一种解法：分别在建好的图中的每一个连通块中跑最小生成树，如果当前连通块已经跑完了就跳转到下一个连通块。
关键代码：
for i:=1 to n do d[i]:=a[1,i]; d[1]:=0; sum:=0; ans:=0;//d[i]表示第i个点到生成树的距离，sum是桥的数量，ans是桥的总长度 repeat k:=maxlongint; p:=0; for i:=1 to n do if(d[i]<k)and(d[i]>0)then begin k:=d[i]; p:=i; end; if p=0 then begin\\跳转到下一个连通块 i:=1; while(d[i]=0)and(i<=n)do inc(i); if i>n then break else begin d[i]:=0; for j:=1 to n do if(d[j]>0)and(d[j]>a[i,j])then d[j]:=a[i,j]; continue; end; end; ans:=ans+d[p]; inc(sum); d[p]:=0; for i:=1 to n do if d[i]>a[p,i] then d[i]:=a[p,i]; until false; writeln(sum,‘ ‘,ans);\\输出答案
然后我去看了看题解，发现了另外一种简单得多的方法：建假枝
在数据中，可能有多个建筑物，但是只要另外建一个点，将它与代表每个建筑物的点连起来（假枝），这样图就会变连通，在统计时，只要忽略假枝就能得出正确的解。
关键代码：
for i:=1 to sum do begin\\建假枝 a[i,sum+1]:=1<<25; a[sum+1,i]:=1<<25; end; writeln(sum); n:=sum+1; for i:=1 to n do d[i]:=a[1,i]; d[1]:=0; sum:=0; ans:=0; repeat k:=maxlongint; p:=0; for i:=1 to n do if(d[i]<k)and(d[i]>0)then begin k:=d[i]; p:=i; end; if p=0 then break; if d[p]<1<<25 then begin\\判断是否为假枝 ans:=ans+d[p]; inc(sum); end; d[p]:=0; for i:=1 to n do if d[i]>a[p,i] then d[i]:=a[p,i]; until false; writeln(sum,‘ ‘,ans);
原文：http://www.cnblogs.com/quzhizhou/p/6285338.html
