原题传送门http://www.lydsy.com/JudgeOnline/problem.php?id=1601
最小生成树的比较水的题，我们只需要加一个源点，连向所有的点，边权为每个点建水库的代价
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
var
n :longint;
pre, other, len :array[..] of longint;
tot :longint;
father :array[..] of longint;
ans :longint; procedure swap(var a,b:longint);
var
c :longint;
begin
c:=a; a:=b; b:=c;
end; procedure qs(low,high:longint);
var
i, j, x :longint;
begin
i:=low; j:=high; x:=len[(i+j) div ];
while i<j do
begin
while len[i]<x do inc(i);
while len[j]>x do dec(j);
if i<=j then
begin
swap(len[i],len[j]);
swap(pre[i],pre[j]);
swap(other[i],other[j]);
inc(i); dec(j);
end;
end;
if i<high then qs(i,high);
if j>low then qs(low,j);
end; procedure init;
var
i, j :longint;
x :longint; begin
read(n);
for i:= to n do
begin
inc(tot);
pre[tot]:=n+;
other[tot]:=i;
read(len[tot]);
end;
for i:= to n do
for j:= to n do
if i<>j then
begin
inc(tot);
pre[tot]:=i;
other[tot]:=j;
read(len[tot]);
end else read(x);
qs(,tot);
end; function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end; procedure main;
var
i :longint;
x, y, fx, fy :longint; begin
for i:= to n+ do father[i]:=i;
for i:= to tot do
begin
x:=pre[i]; y:=other[i];
fx:=getfather(x);
fy:=getfather(y);
if fx<>fy then
begin
inc(ans,len[i]);
father[fx]:=fy;
end;
end;
writeln(ans);
end; begin
init;
main;
end.