这题目郁闷了整整一天，虽然看了黑书上的解释，解题的思路也基本了解，但实现代码仍是一条漫长的路呀
算法流程：
假设V0为被限制的点，即公园，
（1）找{V1,V2,....,Vn}所有的联通分量，求出每个连通分量的最小生成树Ti。
（2）在每个连通分量中，选择V0相邻的最小边，得到Ht。Min<--Ht,V<--cost(Ht)。时间复杂度为O（n）。
（3）循环i<--t+1 to k do
在H(i-1)上选择“差额最小添加操作”，添加并删除一条边得到Hi，令V<V+cost(添边)-cost(删边)，
若V<Min，令Min<--V；如果找不到“差额最小添删操作”则break；
（4）输出Min
注意：
构造最小生成树有个贪心的方法，具体证明见黑书302页。不妨设，现在0号结点还剩度m，那么我们如果加一条0至其它一点的边，必定会存在环，此时肯定要去掉一条环上最大的一条边，至于连接0和哪个结点的边，就要枚举了，判断连哪个结点总权值减小的最大，如此进行m次即可。不过，枚举+找最长的边，时间复杂度为O(n^2)了，最多k次，总的是O(k*n^2)。优化是每次加入0至某个点的一条边时都更新从这条边能到达的其它点的路径的最大值。然后枚举时只要直接判断就行，找到加的那点后，加边时再更新其能到的点的最大值。这两个操作是并行的，时间复杂度为O(n)，成功的将时间复杂度降为O(k*n)
#include<iostream>
#include<string>
#include<map>
using namespace std;
int n,num,kk,g[25][25],d[25],pre[25],ans;
bool flag[25],link[25][25];
//link[][]数组保存各个连通分量中构造的最小生成树的线段
struct point
{
int u,v,maxl;
}p[50];//保存当前节点到0路径上的最长边
map<string ,int> name;
map<string ,int>::iterator t1,t2;
void prim(int ss)
{
flag[ss]=true;
memset(pre,-1,sizeof(pre));
for(int i=1;i<num;i++)
{
d[i]=g[ss][i];
pre[i]=ss;
}
while(1)
{
int tmp=INT_MAX,t=ss;
for(int i=1;i<num;i++)
{
if(!flag[i]&&d[i]!=-1&&d[i]<tmp)
t=i,tmp=d[i];
}
if(t==ss) break;//该连通分量构造最小生成树完成
if(g[0][t]!=-1&&(g[0][kk]==-1||g[0][kk]>g[0][t]))//当前节点到0的边最短，kk保存到该连通分量到0距离最近的节点
kk=t;
link[pre[t]][t]=link[t][pre[t]]=true;//保存线段
flag[t]=true;
ans+=d[t];//累加路径
for(int i=1;i<num;i++)
{
if(g[i][t]!=-1&&!flag[i]&&(d[i]==-1||d[i]>g[t][i]))
{
pre[i]=t;//记录前驱，在上面保存线段时有用
d[i]=g[t][i];
}
}
}
}
void DFS(int tt,int t,int u,int v)//深搜，修改当前连通分量中到达0的路径上的最大边
{
//tt 表示 当前节点，t表示前驱，（u，v)表示当前到0路径上最大边
for(int i=1;i<num;i++)
{
if(t!=i&&link[tt][i])
{
if(t==-1||g[tt][i]>=g[u][v])//当前边大于之前保存的最大边
{
p[i].maxl=g[tt][i];//保存最大边的值
p[i].u=tt;
p[i].v=i;
DFS(i,tt,tt,i);
}
else {
p[i].maxl=g[u][v];
p[i].u=u;
p[i].v=v;
DFS(i,tt,u,v);
}
}
}
}
int main()
{
int a,b,k,d;
char s1[20],s2[20];
while(scanf("%d",&n)!=EOF)
{
name.clear();
name.insert(make_pair("Park",0));
num=1;
memset(g,-1,sizeof(g));
memset(flag,false,sizeof(flag));
memset(link,false,sizeof(flag));
for(int i=0;i<n;i++)//构图
{
scanf("%s %s %d",s1,s2,&d);
t1=name.find(s1);
t2=name.find(s2);
if(t1!=name.end()) a=t1->second;
else name.insert(make_pair(s1,num)),a=num++;
if(t2!=name.end()) b=t2->second;
else name.insert(make_pair(s2,num)),b=num++;
if(g[a][b]>d||g[a][b]==-1)
g[a][b]=g[b][a]=d;
}
scanf("%d",&k);
ans=0;
for(int i=1;i<num;i++)
{
if(flag[i]) continue;
k--;
kk=i;
prim(i);
ans+=g[0][kk];//累加路径
link[kk][0]=link[0][kk]=true;//添加一条当前连通分量到达0的最近边
DFS(kk,-1,-1,-1);
}
while(k)
{
k--;
int i=0,temp;
for(int j=1;j<num;j++)//枚举所有节点，找出最大边
{
if(link[0][j]||g[0][j]==-1) continue;//与0 直接相连的边（不能删），或者本身就不相连
if(i<p[j].maxl-g[0][j])//找出当前连通分量中的最长边
temp=j,i=p[j].maxl-g[0][j];
}
if(i==0) continue;
ans-=i;//减掉删边与加边的差值
link[p[temp].u][p[temp].v]=link[p[temp].v][p[temp].u]=false;//删边
link[0][temp]=link[temp][0]=true;//加边
DFS(temp,0,-1,-1);//再次修改当前连通分量的最长边
}
printf("Total miles driven: %d\n",ans);
}
return 0;
}