题意：
矮人虽小却喜欢乘坐巨大的轿车，车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了集中到聚餐地点，矮人A 要么开车到矮人B 家中，留下自己的轿车在矮人B 家，然后乘坐B 的轿车同行；要么直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K 辆轿车。给你一张加权无向图，描述了N 个矮人的家和聚餐地点，求出所有矮人开车最短总路程。
单点K度限制最小生成树
算法步骤：
1.求出除去K度点的最小生成森林，设森林数为m
2.将这m棵树与K度点用每棵树中与K度点距离最短的点相连，生成一个m度最小生成树，总答案为这个生成树的所有边长之和
3.迭代k-m次，尝试将m度生成树扩展为K度生成树，并求出最小生成树的长度
(1)扫描k度点的所有邻接点，（注意，这是扫描的原图） 找到一个点使得(新的生成树中该点到K度点最大边的长度)与（原图中K度点到该点的距离)之差最大。 (注意，该点 不能是生成树中直接与K度点相连的点)
(2) 若（1）找出的差值不大于0，则无须继续往下找，否则，在新的生成树中连接该点到K度点，并将最大边替换掉，然后从该点开始更新最大边。此时，m度生成树变为 m+1度生成树，总答案减去该差值。
(3)循环以上步骤，直到变为K度生成树或者跳出
1. 先求出最小 m 度限制生成树：原图中去掉和 V0 相连的所有边（可以事先存两个图， Ray 的方法是一个邻接矩阵，一个邻接表，用方便枚举边的邻接表来构造新图），得到 m 个连通分量，则这 m 个连通分量必须通过 v0 来连接，所以，在图 G
的所有生成树中 dT(v0)≥m 。也就是说，当 k<m 时，问题无解。对每个连通分量求一次最小生成树（哪个算法都行），对于每个连通分量 V’ ，用一条与 V0 直接连接的最小的边把它与 V0 点连接起来，使其整体成为一个生成树。于是，我们就得到了一个 m 度限制生成树，不难证明，这就是最小 m 度限制生成树。
2. 由最小 m 度限制生成树得到最小 m+1 度限制生成树;：连接和 V0 相邻的点 v ，则可以知道一定会有一个环出现（因为原来是一个生成树），只要找到这个环上的最大权边（不能与 v0 点直接相连）并删除，就可以得到一个 m+1 度限制生成树，枚举所有和
V0 相邻点 v ，找到替换后，增加权值最小的一次替换 (当然，找不到这样的边时，就说明已经求出) ，就可以求得 m+1 度限制生成树。。如果每添加一条边，都需要对环上的边一一枚举，时间复杂度将比较高（但这个题数据比较小，所以这样也没问题，事实上，直接枚举都能过这个题），这里，用动态规划解决。设 Best(v) 为路径 v0—v 上与 v0 无关联且权值最大的边。定义 father(v) 为 v 的父结点，由此可以得到动态转移方程： Best(v)=max(Best(father(v)),ω(father(v),v))
，边界条件为 Best[v0]=-∞ (因为我们每次寻找的是最大边，所以 -∞ 不会被考虑) ，Best[v’]=-∞| (v0,v’)∈E(T) 。
3. 当 dT(v0)=k 时停止(即当 V0 的度为 k 的时候停止)，但不一定 k 的时候最优。
#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int maxm = 100005;
const int INF = 1e9;
struct node
{
int v, w, next;
}edge[maxm];
struct Edge
{
int u, v, w;
Edge(){}
Edge(int u, int v, int w):u(u),v(v),w(w){}
}mx[maxn];//用于存储每个点到park点的最大边
int n, m, k, sum;//sum为结果
int e, head[maxn], vis[maxn], dis[maxn], use[maxn][maxn];
//head用于邻接表 vis是标记数组 dis用于求最小生成树 use用来标记两点之间是否有边
int blocks, size[maxn], belong[maxn], pre[maxn];
//blocks表示去除park后有几个连通块 size是每个连通块的个数 belong表示该点属于哪个连通块 pre用于在生成树中记录边
int point[maxn], link[maxn]; //point表示每个连通块中与park点最近的点 link则是该点与park点的距离
map<string, int>mp; //用于映射名字
void init()
{
e = 0, n = 1;
blocks = 0, sum = 0;
memset(head, -1, sizeof head );
memset(vis, 0, sizeof vis );
memset(size, 0, sizeof size );
memset(use, 0, sizeof use );
for(int i = 1; i < maxn; i++) mx[i].w = 0;
memset(pre, 0, sizeof pre );
mp.clear();
}
void insert(int x, int y, int w)
{
edge[e].v = y;
edge[e].w = w;
edge[e].next = head[x];
head[x] = e++;
}
int getId(char s[])
{
if(mp.find(s) == mp.end()) mp[s] = ++n;
return mp[s];
}
void dfs(int v) //该dfs将图分成了一些连通块
{
vis[v] = 1;
size[blocks]++;
belong[v] = blocks;
for(int i = head[v]; i != -1; i = edge[i].next)
if(!vis[edge[i].v]) dfs(edge[i].v);
}
void prim(int cur) //对某个连通块求最小生成树
{
for(int i = 1; i <= n; i++) dis[i] = INF;
for(int i = 1; i <= n; i++) //设置块内某点为起点来求生成树
if(belong[i] == cur)
{
dis[i] = 0;
break;
}
for(int i = 1; i <= size[cur]; i++) //循环次数为该块的顶点数，因为这与一般的求MST略微不同
{
int mi = INF, pos = -1;
for(int j = 1; j <= n; j++)
if(pre[j] != -1 && mi > dis[j])
mi = dis[j], pos = j;
if(pos != -1)
{
sum += mi;
use[pos][pre[pos]] = use[pre[pos]][pos] = 1; //标记生成树中所用的边
pre[pos] = -1;
for(int j = head[pos]; j != -1; j = edge[j].next)
if(pre[edge[j].v] != -1 && dis[edge[j].v] > edge[j].w)
{
dis[edge[j].v] = edge[j].w;
pre[edge[j].v] = pos;
}
}
}
}
void getMax(int v, int fa, int w) //该函数用于更新新的生成树中点到park点的最大边
{
pre[v] = fa;
if(mx[fa].w > w) mx[v] = mx[fa];
else mx[v] = Edge(v, fa, w);
for(int i = head[v]; i != -1; i = edge[i].next)
if(use[v][edge[i].v] && edge[i].v != fa) getMax(edge[i].v, v, edge[i].w); //必须是生成树中的边并且不是回边才往下搜
}
void GetMdegreeMST()
{
vis[1] = 1;
for(int i = 2; i <= n; i++) //求连通块
if(!vis[i])
{
blocks++;
dfs(i);
}
pre[1] = -1;
for(int i = 1; i <= blocks; i++) prim(i);
for(int i = 1; i <= n; i++) link[i] = INF;
for(int i = head[1]; i != -1; i = edge[i].next) //生成一棵m度的生成树
if(link[belong[edge[i].v]] > edge[i].w)
{
link[belong[edge[i].v]] = edge[i].w;
point[belong[edge[i].v]] = edge[i].v;
}
for(int i = 1; i <= blocks; i++) //将park点与每个连通块中与其最近的点相连，并且标记边
{
sum += link[i];
use[1][point[i]] = use[point[i]][1] = 1;
}
}
void slove()
{
int degree = blocks;
getMax(1, 0, 0); //首先从park点出发求一遍最大边
while(degree < k) //尝试迭代 k - degree次
{
int maxval = 0, pos = 0, w;
for(int i = head[1]; i != -1; i = edge[i].next) //用于找到差值最大的点
if(!use[1][edge[i].v] && mx[edge[i].v].w - edge[i].w > maxval)
{
maxval = mx[edge[i].v].w - edge[i].w, pos = edge[i].v;
w = edge[i].w;
}
if(!pos) break;
sum -= maxval;//更新答案
degree++;
use[mx[pos].u][mx[pos].v] = use[mx[pos].v][mx[pos].u] = 0;//将最大边删除
use[1][pos] = use[pos][1] = 1;
getMax(pos, 1, w);//更新最大边
}
}
int main()
{
char s1[55], s2[55];
int w;
scanf("%d", &m);
init();
mp["Park"] = 1;
for(int i = 0; i < m; i++)
{
scanf("%s%s%d", s1, s2, &w);
insert(getId(s1), getId(s2), w);
insert(getId(s2), getId(s1), w);
}
scanf("%d", &k);
GetMdegreeMST();
slove();
printf("Total miles driven: %d\n", sum);
return 0;
}