题目描述：
度限制最小生成树
解题报告：

图中的某些点在生成树的时候对它的度有限制（不能超过多少），这个是NP问题。

但是如果只对一个点sta做度的限制，还是可以解的。

设原无向图联通，要求sta点的度不能超过k（或者等于k）的情况下，最小生成树是多少。

步骤如下：

1：刨去和sta点以及和他相关的边，同时求出多个最小生成树。

2：从小到大遍历sta的边，满足不构成环（并查集）的情况下连边，统计连了多少条边mcount。

mcount就是除了点sta有几个联通分量（最小生成树）。

3：如果k < mcount,直接无解。

4：构造best数组，best[i]表示连接sta和i后，构成的环中的权值最大的边的编号(边不和sta相邻)。

5：扫描sta没有连接的边，设权值为val，找出val – best[e[i].to]最小的。

6：更新答案ans = ans + val – best[to],这个就是sta度为mcount+1的最小生成树。

7：mcount++，然后重复4。

#include<iostream>

#include<cstring>

#include<vector>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<map>

using namespace std;

typedef int Jeo;

#define SIZE 23

 

vector<int> stav;

struct pint{int from, to; Jeo val;}tmpe[10000000];//生成树排序用

bool cmp(pint a, pint b){return a.val < b.val;}

struct edge{int to, next, flag; Jeo val;}e[10000000];//实际的边

int v[SIZE], cnt, tmpcnt, sta, f[SIZE], best[SIZE], mcount;//sta点最小的度

void insert(int from, int to, Jeo val)

{

    e[cnt].flag = 0;//flag = 1表示不可用,不存在条边

    e[cnt].val = val;e[cnt].next = v[from];e[cnt].to = to;v[from] = cnt++;

    e[cnt].flag = 0;

    e[cnt].val = val;e[cnt].next = v[to];e[cnt].to = from;v[to] = cnt++;

}

int find(int pos)

{

    if (f[pos] == -1) return pos;

    return f[pos] = find(f[pos]);

}

bool un(int a, int b)

{

    int fa = find(a), fb = find(b);

    if (fa == fb) return false;

    f[fa] = fb;return true;

}

Jeo kruskal(int sta)//度限制点,此部分和编号起点无关，不用修改

{

    memset(f, -1, sizeof(f));

    memset(v, -1, sizeof(v)); cnt = 0;

    sort(tmpe, tmpe + tmpcnt, cmp); Jeo ans = 0;

    stav.clear();

    for(int i = 0; i < tmpcnt; i++)//刨去

        if (tmpe[i].from == sta || tmpe[i].to == sta) stav.push_back(i);

        else if (un(tmpe[i].from, tmpe[i].to))

        {

            insert(tmpe[i].from, tmpe[i].to, tmpe[i].val);

            ans += tmpe[i].val;

        }

    mcount = 0;

    for(int i = stav.size() - 1; i >= 0; i--)

        insert(tmpe[stav[i]].from, tmpe[stav[i]].to, tmpe[stav[i]].val);

    for(int i = v[sta]; i != -1; i = e[i].next)

        if (un(sta, e[i].to))

        {

            mcount++;

            ans += e[i].val;

        }else e[i].flag = e[i ^ 1].flag = 1;

    return ans;

}

void GetBest(int id, int fa, int sta, int eid)

{

    if (id != sta && fa != sta)

    {

        best[id] = best[fa];

        if (best[id] == -1 || e[eid].val > e[best[id]].val)

            best[id] = eid;

    }

    for(int i = v[id]; i != -1; i = e[i].next)

        if (e[i].flag == 0 && e[i].to != fa)

            GetBest(e[i].to, id, sta, i);

}

Jeo jeogia(int sta, int k)

{

    Jeo ans = kruskal(sta);

    if (k < mcount) return -1;//-1为不存在，如果需要，改成其他值

    Jeo tmpans = ans;

    while(mcount < k)

    {

        memset(best, -1, sizeof(best));

        GetBest(sta, -1, sta, 0);

        Jeo mmin = 10000000; int minid = -1;

        for(int i = v[sta]; i != -1; i = e[i].next) if (e[i].flag == 1)

            if (best[e[i].to] != -1)

            {

                Jeo val = e[i].val - e[best[e[i].to]].val;

                if (val < mmin){mmin = val; minid = i;}

            }

        if (minid == -1) break;

        tmpans += mmin;

        if (tmpans < ans) ans = tmpans;

        e[minid].flag = e[minid^1].flag = 0;

        e[best[e[minid].to]].flag = e[best[e[minid].to]^1].flag = 1;

        mcount++;

    }

    return ans;

}

int n, k;

map<string, int> g;

int main()

{

    while(scanf("%d", &n) != EOF)

    {

        int id = 1;

        g.clear();

        for(int i = 0; i < n; i++)

        {

            string a, b; int c;

            cin >> a >> b; cin >> c;

            int id1 = g[a];

            if (id1 == 0) id1 = g[a] = id++;

            int id2 = g[b];

            if (id2 == 0) id2 = g[b] = id++;

            tmpe[i].from = id1; tmpe[i].to = id2; tmpe[i].val = c;

        }

        tmpcnt = n;

        scanf("%d", &k);

        int ans = jeogia(g["Park"], k);

        printf("Total miles driven: %d\n", ans);

    }

return 0;

}