【题意】
k度生成树。
【输入】
第一行：n条边
接下来n行描述边
Park为限度点
【输出】
”Total miles driven: “+最小生成树权值
比较麻烦的一道题
写了4,336 字节
组织的可能不是太好
单纯的讲一下做法
证明黑书上有
1、把跟限度点之间边去掉后生成最小生成树，得到一片森林
2、对于森林里的每棵树，选其中跟限度点有边且该边权值最小的连上
如果有n棵树，则现在则为n度最小生成树
3、接下来就是利用增加度来尝试减少费用了
尝试每条与限度点相连的边，连上该条边理所应当的需要剪短一条从该点到限度点路径上的边
当然是减最大的。
所以每次剪之前，可以做一遍dfs来确定每个点到限度点路径上权值最大的边
总体复杂度O(kn)
就是这样，感觉说的非常不清，不愧是语文期末94的人啊。
program poj1639;
type
node=record
x,y,c:longint;
end;
var
n,i,j,k,t,tot,x,y,c,no,all,ans,now,minn,u,v,maxn:longint;
order,a,b:string;
line:array [0..10001] of node;
temp:node;
trie:array [0..10001,'a'..'z'] of longint;
max,incr,father,who:array [-1..10001] of longint;
nn,last,roo,next,point,cost:array [-1..10001] of longint;
yes:array [-1..10001] of boolean;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
function find (st:string):longint;
var
i,k:longint;
begin
i:=0;
for k:=1 to length(st) do
begin
if trie[i][st[k]]=0 then
begin
inc(tot);
trie[i][st[k]]:=tot;
end;
i:=trie[i][st[k]];
end;
if who[i]=0 then
begin
inc(no);
who[i]:=no;
end;
exit(who[i]);
end;
procedure qsort (s,e:longint);
var
i,j,k:longint;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=line[(s+e) div 2].c;
while i<=j do
begin
while (i<=j)and(line[i].c<k) do inc(i);
while (i<=j)and(line[j].c>k) do dec(j);
if i>j then break;
temp:=line[i];
line[i]:=line[j];
line[j]:=temp;
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;
function root (now:longint):longint;
begin
if father[now]=0 then exit(now);
father[now]:=root(father[now]);
exit(father[now]);
end;
procedure connect (s,e,c,ll:longint);
begin
inc(all);
point[all]:=e;
cost[all]:=c;
next[all]:=roo[s];
last[roo[s]]:=all;
roo[s]:=all;
nn[all]:=ll;
end;
procedure deletee (now,wh:longint);
begin
if next[now]<>0 then last[next[now]]:=last[now];
if last[now]<>0 then next[last[now]]:=next[now];
if roo[wh]=now then roo[wh]:=next[now];
end;
procedure dfs (now,maxn:longint);
var
i:longint;
begin
yes[now]:=true;
i:=roo[now];
max[now]:=maxn;
while i<>0 do
begin
if not yes[point[i]] then
if cost[i]>cost[maxn] then dfs(point[i],i)
else dfs(point[i],maxn);
i:=next[i];
end;
end;
begin
readln(n);
trie[0,'p']:=1;
trie[1,'a']:=2;
trie[2,'r']:=3;
trie[3,'k']:=4;
tot:=4;
no:=0;
who[4]:=-1;
for i:=1 to n do
begin
readln(order);
a:=copy(order,1,pos(' ',order)-1);
delete(order,1,pos(' ',order));
b:=copy(order,1,pos(' ',order)-1);
delete(order,1,pos(' ',order));
val(order,line[i].c,c);
for j:=1 to length(a) do
if a[j]<='Z' then a[j]:=chr(ord(a[j])+32);
for j:=1 to length(b) do
if b[j]<='Z' then b[j]:=chr(ord(b[j])+32);
line[i].x:=find(a);
line[i].y:=find(b);
if line[i].x>line[i].y then swap(line[i].x,line[i].y);
end;
read(t);
qsort(1,n);
all:=0;
now:=0;
for i:=1 to n do
if (line[i].x<>-1)and(line[i].y<>-1)and(root(line[i].x)<>root(line[i].y)) then
begin
father[root(line[i].x)]:=root(line[i].y);
now:=now+line[i].c;
connect(line[i].x,line[i].y,line[i].c,all+2);
connect(line[i].y,line[i].x,line[i].c,all);
end;
fillchar(incr,sizeof(incr),0);
fillchar(yes,sizeof(yes),false);
k:=0;
for i:=1 to n do
if ((line[i].x=-1)or(line[i].y=-1))and(not yes[root(line[i].x+line[i].y+1)]) then
begin
inc(k);
yes[root(line[i].x+line[i].y+1)]:=true;
incr[root(line[i].x+line[i].y+1)]:=line[i].c;
now:=now+line[i].c;
connect(line[i].x,line[i].y,line[i].c,all+2);
connect(line[i].y,line[i].x,line[i].c,all);
end;
line[0].c:=-maxlongint;
ans:=now;
for i:=k+1 to t do
begin
fillchar(yes,sizeof(yes),false);
maxn:=0;
dfs(-1,0);
for j:=1 to n do
if (line[j].x=-1)and(cost[max[line[j].y]]-line[j].c>maxn) then
begin
maxn:=cost[max[line[j].y]]-line[j].c;
u:=line[j].y;
v:=j;
end;
if maxn=0 then break;
now:=now-maxn;
if now<ans then ans:=now;
deletee(max[u],point[nn[max[u]]]);
deletee(nn[max[u]],u);
connect(line[v].x,line[v].y,line[v].c,all+2);
connect(line[v].y,line[v].x,line[v].c,all);
end;
writeln('Total miles driven: ',ans);
end.