题目描述
矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了
集中到聚餐地点，矮人A 有以下两种选择
1）开车到矮人B家中，留下自己的轿车在矮人B家，然后乘坐B的轿车同行
2）直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K辆轿车。
现在给你一张加权无向图，它描述了N个矮人的家和聚餐地点，要你求出所有矮人开车的最短总路程。
输入格式
第一行是整数M，接下来M行描述了M条道路。
每行形式如同：S1 S2 x，S1和S2均是由字母组成长度不超过20的字符串
(特别地，当该字符串为”Park”时表示聚餐地点)，x是整数，表示从S1到S2的距离。
最后一行包含单独的整数k.
输出格式
仅一行，形式如同：
Total miles driven: xxx
xxx是整数，表示最短总路程。
设Park为1节点。
先不考虑1节点，我们求出去掉1节点之后的图的最小生成树森林。设森林包含x棵树，那么我们从每棵树上都找出一条最短的连向1节点的边连起来。
然后我们可以再给1节点加上k-x条边。扫描1节点连接的所有还没被加入生成树的边，设其边长为p，两个端点为u,v，我们求出u和v在生成树上的路径中的最大边，设其边长为q。如果p-q<0，那么把q删去，把p加上。直到扫描完所有边或者加了k-x条边时，我们便得到了题目所求的生成树。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#define maxn 31
using namespace std;
struct edge{
int u,v,w;
bool operator<(const edge &e)const{ return w<e.w; }
}e[maxn*maxn],dp[maxn];
int key[maxn],minedge[maxn];
int fa[maxn],g[maxn][maxn];
bool tree[maxn][maxn];
int n,m,k,ans;
map<string,int> id;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int get(int x){ return fa[x]==x?x:fa[x]=get(fa[x]); }
inline void kruskal(){
sort(e+1,e+1+m);
for(register int i=1;i<=n;i++) fa[i]=i;
for(register int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(u==1||v==1||get(u)==get(v)) continue;
fa[get(u)]=get(v),tree[u][v]=tree[v][u]=true;
ans+=w;
}
}
void dfs(int u,int pre){
for(register int i=2;i<=n;i++) if(tree[u][i]){
if(i==pre) continue;
if(dp[i].w==-1){
if(dp[u].w>g[u][i]) dp[i]=dp[u];
else{
dp[i].w=g[u][i],dp[i].u=u,dp[i].v=i;
}
}
dfs(i,u);
}
}
inline void solve(){
register int cnt=0;
for(register int i=2;i<=n;i++) if(g[i][1]!=0x3f3f3f3f){
int col=get(i);
if(g[i][1]<minedge[col]) minedge[col]=g[i][1],key[col]=i;
}
for(register int i=1;i<=n;i++) if(minedge[i]!=0x3f3f3f3f){
cnt++,tree[key[i]][1]=tree[1][key[i]]=true;
ans+=g[1][key[i]];
}
for(register int i=cnt+1;i<=k;i++){
memset(dp,-1,sizeof dp);
dp[1].w=-0x3f3f3f3f;
for(register int j=2;j<=n;j++) if(tree[1][j]) dp[j].w=-0x3f3f3f3f;
dfs(1,1);
int d,mini=0x3f3f3f3f;
for(register int j=2;j<=n;j++) if(mini>g[1][j]-dp[j].w){
mini=g[1][j]-dp[j].w,d=j;
}
if(mini>=0) continue;
tree[1][d]=tree[d][1]=true,tree[dp[d].u][dp[d].v]=tree[dp[d].v][dp[d].u]=false;
ans+=mini;
}
}
int main(){
memset(g,0x3f,sizeof g),memset(minedge,0x3f,sizeof minedge);
m=read(),id["Park"]=++n;
for(register int i=1;i<=m;i++){
string a,b; cin>>a>>b;
if(!id[a]) id[a]=++n;
if(!id[b]) id[b]=++n;
e[i].u=id[a],e[i].v=id[b],e[i].w=read();
g[e[i].u][e[i].v]=g[e[i].v][e[i].u]=min(g[e[i].u][e[i].v],e[i].w);
}
k=read();
kruskal(),solve();
printf("Total miles driven: %d
", ans);
return 0;
}