题目

题目描述

一群小丑演员，以其出色的柔术表演，可以无限量的钻进同一辆汽车中，而闻名世界。

现在他们想要去公园玩耍，但是他们的经费非常紧缺。

他们将乘车前往公园，为了减少花费，他们决定选择一种合理的乘车方式，可以使得他们去往公园需要的所有汽车行驶的总公里数最少。

为此，他们愿意通过很多人挤在同一辆车的方式，来减少汽车行驶的总花销。

由此，他们可以很多人驾车到某一个兄弟的家里，然后所有人都钻进一辆车里，再继续前进。

公园的停车场能停放的车的数量有限，而且因为公园有入场费，所以一旦一辆车子进入到公园内，就必须停在那里，不能再去接其他人。

现在请你想出一种方法，可以使得他们全都到达公园的情况下，所有汽车行驶的总路程最少。

输入格式

第一行包含整数n，表示人和人之间或人和公园之间的道路的总数量。

接下来n行，每行包含两个字符串A、B和一个整数L，用以描述人A和人B之前存在道路，路长为L，或者描述某人和公园之间存在道路，路长为L。

道路都是双向的，并且人数不超过20，表示人的名字的字符串长度不超过10，公园用“Park”表示。

再接下来一行，包含整数s，表示公园的最大停车数量。

你可以假设每个人的家都有一条通往公园的道路。

输出格式
输出“Total miles driven: xxx”，其中xxx表示所有汽车行驶的总路程。

样例

样例输入
10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3
样例输出
Total miles driven: 183

题解

这道题思路比较好想，但有点难打（细节巨多）。

首先题意可以转化为：给定一张n个点，m条边的无向图，求出一颗最小生成树，满足1号节点的度数不超过给定整数s。

1.我们先将名字用map转化为节点，用邻接表储存。

2.去掉1号节点，跑一个Kruskal，让离1号节点近的当根节点，注意用vis标记哪些边在树上，这样得到一个森林，每一棵树都为最小生成树，共有t棵树。

3.dfs找到每棵树中每个点到根节点的路径上最长边用结构体记录（每棵树从根节点dfs，只找一次）。

4.接着枚举每一个根节点，将其与1号连接（注意更新答案和vis）。

5.再考虑从每棵树根节点出发的每条不在树上的边（1，x）边权为z，运用之前找到的每条路径上的最长边（u，v)，边权为w。从节点2至n枚举，最小化（z，w），若（z-w）> 0，则用（1，x）替换（u，v)。记住用dfs从x开始更新，vis也要更新。

6.第五条重复s-t次或w-z<0。

#include<bits/stdc++.h>
using namespace std;
const int M=1e3+5;
int ans,n,cnt,tot,k;
int fa[M],vis[M][M],d[M][M];
struct edge{int u,v,w;edge(){}edge(int V,int W){v=V;w=W;}
}p[M],t[M];
void Makeset(){for(int i=1;i<=tot;i++){fa[i]=i;}
}
int Findset(int x){if(fa[x]!=x){fa[x]=Findset(fa[x]);}return fa[x];
}
void Unionset(int u,int v){if(d[u][1]<d[v][1]){fa[v]=u;}else {fa[u]=v;}}
bool cmp(edge e1,edge e2){return e1.w<e2.w;}
void init(){char s1[20],s2[20];int U,V,W;map<string,int> name;	map<string,int>::iterator it1,it2;name["Park"]=++tot;//转化成数字memset(d,0x3f,sizeof(d));	scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s %s %d",&s1,&s2,&W);it1=name.find(s1);it2=name.find(s2);if(it1!=name.end())U=it1->second;//出现过else {name[s1]=++tot;//第一次出现U=tot;}if(it2!=name.end())V=it2->second;else {name[s2]=++tot;V=tot;}p[++cnt].u=U;p[cnt].v=V;p[cnt].w=W;d[U][V]=W,d[V][U]=W;//邻接表}	scanf("%d",&k);
}
void Kruskal(){//板子Makeset();sort(p+1,p+cnt+1,cmp);for(int i=1;i<=cnt;i++){if(p[i].u==1||p[i].v==1) {continue;}int x1=Findset(p[i].u);int x2=Findset(p[i].v);if(x1!=x2){vis[p[i].u][p[i].v]=1,vis[p[i].v][p[i].u]=1;//注意记录vis      	Unionset(x1,x2);ans+=p[i].w;}}
}
void dfs(int now,int last,int u,int v){for(int i=2;i<=tot;i++){if(last!=i&&vis[now][i]){//在树上且不重复if(last==-1||d[now][i]>d[u][v]){//找最长的边t[i].u=now,t[i].v=i,t[i].w=d[now][i];dfs(i,now,now,i);	}else {			t[i].u=u,t[i].v=v,t[i].w=d[u][v];dfs(i,now,u,v);}}		}
}
void work(){memset(vis,0,sizeof(vis));Kruskal();for(int i=2;i<=tot;i++){if(fa[i]==i)//每棵树只找一次，从根节点开始找dfs(i,-1,-1,-1);}for(int i=2;i<=tot;i++){if(fa[i]==i) {//将每棵树连接节点1k--;//节点1剩余度数减少ans+=d[1][i];//更新答案fa[i]=1;vis[1][i]=1,vis[i][1]=1;//更新vis}}while(k--){//还有k点度数可用int ex,_ans=0;for(int i=2;i<=tot;i++){if(d[1][i]==0x3f3f3f3f||vis[1][i]==1){//无边或在树上continue;}			if(_ans<t[i].w-d[i][1]){//求最小_ans=t[i].w-d[i][1];ex=i;}}if(_ans==0) break;//已最优ans-=_ans;vis[1][ex]=1,vis[ex][1]=1;//删边，加边vis[t[ex].u][t[ex].v]=0,vis[t[ex].v][t[ex].u]=0;dfs(ex,1,-1,-1);//从ex开始更新最长路径}printf("Total miles driven: %d\n",ans);
}
int main(){init();work();   return 0;
}