内容目录
题目大意:最小生成树
建源点0与各点连线的权为建水库的大小。
Program aa; var n,i,j,p:longint; u,v,w:array[0..100000] of longint; size,cost:longint; father:array[0..300] of longint; procedure qsort(l,r:longint); var i,j,m,p:longint; begin i:=l;j:=r;m:=w[(l+r) shr 1]; repeat while w[i]<m do inc(i); while w[j]>m do dec(j); if i<=j then begin p:=w[i];w[i]:=w[j];w[j]:=p; p:=u[i];u[i]:=u[j];u[j]:=p; p:=v[i];v[i]:=v[j];v[j]:=p; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; function getfather(x:longint):longint; begin if father[x]=x then exit(x); father[x]:=getfather(father[x]); exit(father[x]); end; begin read(n); for i:=1 to n do begin read(w[i]); u[i]:=0;v[i]:=i; end; size:=n; for i:=1 to n do for j:=1 to n do begin read(p); if i=j then continue; inc(size); u[size]:=i;v[size]:=j;w[size]:=p; end; qsort(1,size); cost:=0; for i:=0 to n do father[i]:=i; for i:=1 to size do begin if (getfather(u[i])<>getfather(v[i])) then begin inc(cost,w[i]); father[getfather(u[i])]:=father[getfather(v[i])]; end; end; writeln(cost); end.