今天了解了一下最小度限制生成树。这个问题的本质依旧是生成树，但是对于某个点的度给定限制。也就是连到该点上的边不能超过限制的数量limit。
具体的解决过程和相关的证明可以看一下《最小生成树问题的扩展》这篇论文。这里简单讲一下解决问题的流程也方便我之后来复习。
1，用除去和有限制的点相连的以外的边做最小生成树。这个时候可能不能保证所有点都连通，那么可能会出现几个连通块。如果连通块的数量超过了限制的度数，那么这些连通块显然不能连通。这个条件下，问题无解。
2，选出各联通块与限制点相连权值最小的边与限制点相连，保证所有点连通
3，假设完成2操作后限制点的度已经为d，循环limit-d次，每次先求出从限制点到各点的路径上的边的最大权值。然后遍历所有与限制点相连但是没有加入到树中的边，如果选择这条边那么生成树的值变化为改边的权值减去从限制点到该边相连的另一点的路径上的最大权值 我们记作 change。选出最小的change值，如果某次循环中change的值为非负数。说明当前求得的最小生成树已经是满足条件的最优生成树，跳出循环。否则生成树的大小加上change值，并对图做修改。
4，得出答案
POJ1639 http://poj.org/problem?id=1639 最小度限制生成树模板题
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<algorithm> using namespace std; const int maxn = 33; const int INF = 1e9+7; map<string, int> Map; struct Edge{ int from, to, len; }e[maxn*maxn+100]; Edge dp[maxn*maxn+100]; int G[maxn][maxn], father[maxn]; int limit, n, cnt, ans; bool used[maxn][maxn]; bool cmp(Edge x, Edge y){ return x.len < y.len; } int fnd(int x){ if (father[x] != x) father[x] = fnd(father[x]); return father[x]; } bool uni(int x, int y){ int fx = fnd(x), fy = fnd(y); if (fx == fy) return false; father[fx] = fy; return true; } void kruskal(){ for (int i = 1; i <= n; i++){ int from = e[i].from, to = e[i].to; if (from == 1 || to == 1) continue; if (uni(from, to)){ used[from][to] = used[to][from] = true; ans += e[i].len; } } } int getNum(string s){ if (Map.find(s) == Map.end()){ Map[s] = ++cnt; } return Map[s]; } void init(){ memset(used, false, sizeof(used)); memset(G, -1, sizeof(G)); cnt = 1; ans = 0; Map["Park"] = 1; cin >> n; string s; for (int i = 1; i <= n; i++){ cin >> s; e[i].from = getNum(s); cin >> s; e[i].to = getNum(s); cin >> e[i].len; int from = e[i].from, to = e[i].to; if (G[from][to] == -1) G[from][to] = G[to][from] = e[i].len; else G[from][to] = G[to][from] = min(G[from][to], e[i].len); } for (int i = 1; i <= cnt; i++) father[i] = i; cin >> limit; } void dfs(int node, int pre){ for (int i = 2; i <= cnt; i++) if (i != pre && used[node][i]){ if (dp[i].len == -1){ if (dp[node].len > G[node][i]) dp[i] = dp[node]; else{ dp[i].from = node; dp[i].to = i; dp[i].len = G[node][i]; } } dfs(i, node); } } void solve(){ sort(e+1, e+n+1, cmp); kruskal(); //cout << "ans: " << ans << endl; int Min[maxn], tmp[maxn]; for (int i = 1; i <= cnt; i++) Min[i] = INF; memset(tmp, -1, sizeof(tmp)); for (int i = 2; i <= cnt; i++){ if (G[1][i] == -1) continue; int t = fnd(i); if (G[1][i] < Min[t]){ Min[t] = G[1][i]; tmp[t] = i; } } int t = 0; for (int i = 2; i <= cnt; i++){ if (Min[i] != INF){ ans += G[1][tmp[i]]; used[1][tmp[i]] = used[tmp[i]][1] = true; t++; } } for (int k = t+1; k <= limit; k++){ memset(dp, -1, sizeof(dp)); dp[1].len = -INF; for (int i = 2; i <= cnt; i++){ if (used[1][i]) dp[i].len = -INF; } dfs(1, 1); int tnode = -1, low = INF; for (int i = 2; i <= cnt; i++){ if (G[1][i] != -1){ if (low > G[1][i] - dp[i].len){ low = G[1][i] - dp[i].len; tnode = i; } } } if (low >= 0) break; used[1][tnode] = used[tnode][1] = true; int from = dp[tnode].from, to = dp[tnode].to; used[from][to] = used[to][from] = false; ans += low; } printf("Total miles driven: %d\n", ans); } int main(){ std::ios::sync_with_stdio(false); init(); solve(); return 0; }
