给出一个带边权连通无向图，当中指定一个点V0，要求这个图的一个生成树，使得树中V0点的度数（和V0点关联的边数）刚好为一个指定值P，求满足此条件的边权和最小的生成树。
【算法】（某神犇的论文里有详细证明，这里省略了囧……）
设l[i]为连接图中点V0与点i之间的边的长度（若有多条边取权值最小的，若没有边则为无穷大）。
（1）在图中删除点V0，新的图不一定是连通图，设其有B个连通块；
（2）若P<B则无解，否则转下一步；
（3）对这B个连通块分别求最小生成树，得到一个生成森林。然后在图中重新加入点V0，对每个连通块，找出该连通块内l值最小的点V'，添加边(V0, V')，这样就得到了一棵初始的生成树，或者说，这是V0点度数为B的最小的生成树；
（4）然后就是不断往里面加入与V0相关联的边。从V0点开始，对整棵生成树BFS遍历，对每个点i，找到目前的生成树中从V0到i的路径上权值最大的边，设E_len[i]为这条边的权值，E_No[i]为这条边的编号（由于本沙茶使用的是DL边表，故记录编号），这个东东的求法很容易，省略；
（5）最后，枚举除V0点外的每个点，找到(E_len[i]-l[i])值最大的点i，然后在图中删除边E_No[i]，加入边(V0, i)，这样得到的仍然是原图的生成树，且V0的度数增加1；
（6）重复以上过程(P-B)次即得结果。
【实现注意】
为了编程实现更加方便，注意以下几点：
（1）一开始不加入V0，而不是加入了再删去（但各点l值要在输入时求出）；
（2）一开始不用先求出B的值，而是先求出最小生成森林（用Kruskal，不断加边，直到加到不能再加为止）和初始生成树，再遍历初始生成树得到B值；
（3）由于涉及删边，一定要用DL边表。
【代码】（
PKU1639，注意这题是求V0度数不超过给定值P的最小生成树，简单改装即可）：
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 30, MAXM = 5000, MAXLEN = 20, INF = ~0U >> 2;
struct edge {
int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge0 {
int a, b, len;
} ed0[MAXM];
int n, m, m0 = 0, P, B = 0, l[MAXN], u[MAXN], B_No[MAXN], q[MAXN], E_No[MAXN], E_len[MAXN], res = 0;
string NAMELIST[MAXN];
bool vst[MAXN];
void add_edge0(int a, int b, int len)
{
ed0[m0].a = a; ed0[m0].b = b; ed0[m0++].len = len;
}
void init_d()
{
re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int len)
{
ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
ed[m].a = b; ed[m].b = a; ed[m].len = len; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
n = 1; NAMELIST[0] = "Park"; int m_;
scanf("%d", &m_); char ch = getchar(), s01[MAXLEN], s02[MAXLEN]; int No1, No2, l0, tmp;
re(i, MAXN) l[i] = INF;
re(i, m_) {
scanf("%s %s %d", s01, s02, &l0); ch = getchar();
No1 = -1; re(j, n) if (NAMELIST[j] == s01) {No1 = j; break;} if (No1 == -1) NAMELIST[No1 = n++] = s01;
No2 = -1; re(j, n) if (NAMELIST[j] == s02) {No2 = j; break;} if (No2 == -1) NAMELIST[No2 = n++] = s02;
if (No1 > No2) {tmp = No1; No1 = No2; No2 = tmp;}
if (No1) add_edge0(No1, No2, l0); else if (l0 < l[No2]) l[No2] = l0;
}
scanf("%d", &P);
}
int cmp(const void *s1, const void *s2)
{
return ((edge0 *)s1)->len - ((edge0 *)s2)->len;
}
int find_root(int x)
{
int r = x, r0 = x, tmp;
while (u[r] >= 0) r = u[r];
while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
return r;
}
void uni(int r1, int r2)
{
int sum = u[r1] + u[r2];
if (u[r1] >= u[r2]) {u[r1] = r2; u[r2] = sum;} else {u[r2] = r1; u[r1] = sum;}
}
void prepare()
{
qsort(ed0, m0, 12, cmp);
re2(i, 1, n) u[i] = -1; init_d();
int x1, x2, l0, r1, r2;
re(i, m0) {
x1 = ed0[i].a; x2 = ed0[i].b; l0 = ed0[i].len; r1 = find_root(x1); r2 = find_root(x2);
if (r1 != r2) {uni(r1, r2); add_edge(x1, x2, l0); res += l0;}
}
re2(i, 1, n) B_No[i] = -1;
int Best, Best_No;
re2(i, 1, n) if (B_No[i] == -1) {
B_No[i] = B; Best = l[i]; Best_No = q[0] = i;
int j, k;
for (int front=0, rear=0; front<=rear; front++) {
j = q[front];
for (int p=ed[j].next; p != j; p=ed[p].next) {
k = ed[p].b;
if (B_No[k] == -1) {
B_No[k] = B; q[++rear] = k; if (l[k] < Best) {Best = l[k]; Best_No = k;}
}
}
}
add_edge(0, Best_No, Best); res += Best; B++;
}
}
void solve()
{
vst[0] = 1;
re2(P0, B, P) {
re2(i, 1, n) {E_len[i] = INF; vst[i] = 0;} q[0] = 0;
int i, j, l0;
for (int front=0, rear=0; front<=rear; front++) {
i = q[front];
for (int p=ed[i].next; p != i; p=ed[p].next) {
j = ed[p].b; l0 = ed[p].len;
if (!vst[j]) {
vst[j] = 1; q[++rear] = j;
if (E_len[i] > l0) {E_len[j] = E_len[i]; E_No[j] = E_No[i];} else {E_len[j] = l0; E_No[j] = p;}
}
}
}
int Best = 0, Best_No, Best_v;
re2(i, 1, n) {
l0 = E_len[i] - l[i];
if (l0 > Best) {Best = l0; Best_No = E_No[i]; Best_v = i;};
}
if (Best) {del_edge(Best_No); add_edge(0, Best_v, l[Best_v]); res -= Best;} else break;
}
}
void pri()
{
printf("Total miles driven: %d\n", res);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}