最小限度生成树

图论 生成树

---

简述

最小度限制生成树就是给一个图，求它的满足点vo的度数最大为k的最小生成树.

算法

1. 将v0从图中删除，将得到m个连通分量。
2. 对每个连通分量求最小生成树，假设m个。
3. 从每个连通分量中找与v0关联的权值最小的边，与v0相连接，这样将得到v0的最小m度生成树
4. 如果 k < m 那么这种树是不存在的。
5. 如果 k >= m, 那么考虑构建 m + 1度最小生成树, 将与v0关联的且不在当前的树中的边
6. 如果将其加入树中, 必然会存在一个环，那么删掉该环中与v0不关联的权值最大边，将得到加入该边后的最小生成树，且是m + 1的。
7. 枚举上述 6 的边找树权值最小, 那么即是m + 1度限制的最小生成树。如果 m + 1 度最小生成树的值大于 m 度最小生成树的话直接输出当前 m 度的值即可。
8. 重复5.6.7，直到k 度最小生成树出现。

由上述步骤可知，由 m 度限制生成树拓展为 m + 1 度限制生成树的过程中需要大量的重复运算, 可以运用动态规划来优化。

设 dp(v) 为路径 v0—v 上与 v0 无关联且权值最大的边。定义 father(v) 为 v 的父结点，动态转移方程

$$dp(v)=max(dp(father(v)),ω(father(v),v))$$ 边界条件为 $$dp[v0]=-∞(因为每次寻找的是最大边,所以-∞不会被考虑)，dp[v’]=-∞| (v0,v’)∈E(T)$$

算法实现

并查集 + kruskal;
首先,每个连通分量的的最小生成树可以直接用一个循环,循环着 Kruskal 求出;
这里利用了联通分量间的独立性,对每个连通分量分别求最小生成树,和放在一起求,毫不影响;
而且 kruskral 算法保证了各连通分量边的有序性;
找最小边的时候,可以用动态规划,也可以这么做：
先走一个循环,但我们需要逆过来加边,将与 v0 关联的所有边从小到达排序;
然后将各连通分量连接起来,利用并查集可以保证每个连通分量只有一条边与 v0 相连;
由于边已经从小到达排序,故与每个连通分量相连的边就是每个连通分量与 v0 相连中的最小边;
然后求 m + 1度的最小生成树时,可以直接用DFS,最小生成树要一直求到k度,然后从中找出一个最优值;

例题 POJ 1639

• 题意：
  给出m条边,每条边有两个端点和一个权值;
  求这个图在满足以下条件的情况下的最小生成树:
  在所有点中,有一个特殊点Park,它在求得的最小生成树中的度必须小于等于某个值;

• 示例代码

#include <map>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 50;
const int MAX_INT = (1 << 29);
struct Edge{
    int v, w, nxt;
};
struct Node{
    int u, v, w;
   friend bool operator < (const Node &a, const Node &b){
       return a.w < b.w;
   }
};
int pcnt;
int par[MAXN];
map <string, int> ma;
Node node[MAXN * MAXN], dp[MAXN];
int ecnt, n, m, k;
bool use[MAXN][MAXN];
Edge edge[MAXN * MAXN];
int head[MAXN], vis[MAXN], dis[MAXN];
int Min[MAXN], tmp[MAXN];
void init(){
    ma.clear();
    ecnt = pcnt = 0;
    memset(dp, -1, sizeof(dp));
    memset(use, 0, sizeof(use));
    memset(edge, 0, sizeof(edge));
    memset(node, 0, sizeof(node));
    memset(head, -1, sizeof(head));
    fill(Min, Min + MAXN, MAX_INT);
    for(int i = 0; i < MAXN; i++) par[i] = i;
}
void addEdge(int u, int v, int w){
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt++;
}
int getId(char s[]){
    if(ma.find(s) == ma.end()) ma[s] = ++pcnt;
    else return ma[s];
    return pcnt;
}
int Find(int x){
    if(par[x] != x) par[x] = Find(par[x]);
    return par[x];
}
bool Union(int x, int y){
    int fx = Find(x);
    int fy = Find(y);
    if(fx == fy) return false;
    par[fy] = fx;
    return true;
}
void dfs(int s, int u, int fa){
    for(int i = head[u]; i + 1; i = edge[i].nxt){
        int v = edge[i].v;
        if(v != s && v != fa && use[u][v]){
            if(dp[v].w == -1){
                if(dp[u].w > edge[i].w) dp[v] = dp[u];
                else{
                    dp[v].w = edge[i].w;
                    dp[v].u = u;
                    dp[v].v = v;
                }
            }
            dfs(s, v, u);
        }
    }
}
int kruskal(int s){
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(node[i].u == s || node[i].v == s) continue;
        if(!Union(node[i].u, node[i].v)) continue;
        use[node[i].u][node[i].v] = use[node[i].v][node[i].u] = true;
        ans += node[i].w;
    }
    return ans;
}
int solve(int s){
    sort(node, node + n);
    int ans = kruskal(s);
    for(int i = head[s]; i + 1; i = edge[i].nxt){
        int v = edge[i].v;
        int belong = Find(v);
        if(Min[belong] > edge[i].w){
            tmp[belong] = edge[i].v;
            Min[belong] = edge[i].w;
        }
    }
    int degree = 0;
    for(int i = 1; i <= pcnt; i++){
        if(Min[i] != MAX_INT){
            degree++;
            use[s][tmp[i]] = use[tmp[i]][s] = true;
            ans += Min[i];
        }
    }
    for(int i = degree + 1; i <= k; i++){
        dp[s].w = -MAX_INT;
        for(int j = 2; j <= pcnt; j++)
            if(use[s][j]) dp[j].w = -MAX_INT;
        dfs(s, 1, -1);
        int temp, mi = MAX_INT;
        for(int j = head[s]; j + 1; j = edge[j].nxt){
            if(mi > edge[j].w - dp[edge[j].v].w){
                mi = edge[j].w - dp[edge[j].v].w;
                temp = edge[j].v;
            }
        }
        if(mi >= 0) break;
        use[s][temp] = use[temp][s] = true;
        int u = dp[temp].u;
        int v = dp[temp].v;
        use[u][v] = use[v][u] = false;
        ans += mi;
    }
    return ans;
}
int main(){
    while(scanf("%d", &n) != EOF){
        init();
        int u, v, w;
        char s1[50];
        char s2[50];
        ma["Park"] = ++pcnt;
        for(int i = 0; i < n; i++){
            scanf("%s%s%d", s1, s2, &w);
            u = getId(s1), v = getId(s2);
            addEdge(u, v, w);
            addEdge(v, u, w);
            node[i].u = u, node[i].v = v, node[i].w = w;
        }
        scanf("%d", &k);
        int ans = solve(1);
        printf("Total miles driven: %d\n", ans);
    }
    return 0;
}