給出一個帶邊權(quán)連通無向圖，當(dāng)中指定一個點V0，要求這個圖的一個生成樹，使得樹中V0點的度數(shù)（和V0點關(guān)聯(lián)的邊數(shù)）剛好為一個指定值P，求滿足此條件的邊權(quán)和最小的生成樹。
【算法】（某神犇的論文里有詳細(xì)證明，這里省略了囧……）
設(shè)l[i]為連接圖中點V0與點i之間的邊的長度（若有多條邊取權(quán)值最小的，若沒有邊則為無窮大）。
（1）在圖中刪除點V0，新的圖不一定是連通圖，設(shè)其有B個連通塊；
（2）若P<B則無解，否則轉(zhuǎn)下一步；
（3）對這B個連通塊分別求最小生成樹，得到一個生成森林。然后在圖中重新加入點V0，對每個連通塊，找出該連通塊內(nèi)l值最小的點V'，添加邊(V0, V')，這樣就得到了一棵初始的生成樹，或者說，這是V0點度數(shù)為B的最小的生成樹；
（4）然后就是不斷往里面加入與V0相關(guān)聯(lián)的邊。從V0點開始，對整棵生成樹BFS遍歷，對每個點i，找到目前的生成樹中從V0到i的路徑上權(quán)值最大的邊，設(shè)E_len[i]為這條邊的權(quán)值，E_No[i]為這條邊的編號（由于本沙茶使用的是DL邊表，故記錄編號），這個東東的求法很容易，省略；
（5）最后，枚舉除V0點外的每個點，找到(E_len[i]-l[i])值最大的點i，然后在圖中刪除邊E_No[i]，加入邊(V0, i)，這樣得到的仍然是原圖的生成樹，且V0的度數(shù)增加1；
（6）重復(fù)以上過程(P-B)次即得結(jié)果。
【實現(xiàn)注意】
為了編程實現(xiàn)更加方便，注意以下幾點：
（1）一開始不加入V0，而不是加入了再刪去（但各點l值要在輸入時求出）；
（2）一開始不用先求出B的值，而是先求出最小生成森林（用Kruskal，不斷加邊，直到加到不能再加為止）和初始生成樹，再遍歷初始生成樹得到B值；
（3）由于涉及刪邊，一定要用DL邊表。
【代碼】（
PKU1639，注意這題是求V0度數(shù)不超過給定值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;
}