最小度限制生成树
??? 在一棵生成树中，某个顶点v0的度数<=k称作度限制条件，把满足这一条件的生成树称为度限制生成树，把权值和最小的度限制生成树称为最小度限制生成树。
??? 如果撇开度限制条件，那么就是最小生成树问题。首先，避开度限制条件。假如把最小度限制生成树中所有与v0相关的边都删掉，得到m个连通分量。
??? 具体步骤：
??? 1. 如果k<m，显然无解。
??? 2. 求最小m度限制生成树。
??? 3. 有最小m度限制生成树求最小m+1度限制生成树。
??? 4. 当dT(v0)==k时，停止迭代。
??? 说明：
??? 求最小m度限制生成树时：去掉图中和v0相连的所有边，得到m个连通分量，而这m个连通分量必须通过v0来连接。所以在生成树中，dT(v0)>=m，如果k<m，问题无解。对每个连通分量求最小生成树。对于每个连通分量v'，找到和v0相连的最小边。于是，我们得到了一个最小m度限制生成树。
??? 由最小m度限制生成树得到最小m+1度限制生成树：对于和v0相邻的点v，添加后一定会形成一个环，找到环上权值最大的边，用(v0,v)替换掉。枚举所有和v0相邻的点，找到权值增加最小的一次替换，就可以得到最小m+1度限制生成树。每次枚举的时候都需要找换上不和v0相连的最大边，需要用到动态规划：设best[v]是v0到v路劲上不与v0相连的最大边，定义father[v]是v的父节点，状态转移方程为：
best[v] = max{best[father[v]], w(father[v],v)}
??? 边界条件为best[v0]=INF,best[v']=INF((v0,v')是图中的边)。
?
模型与例题：
1. 考虑下面这个问题：
??? 某地区有n个村庄，左边为(x,y)。现在村庄要建立通讯网络，安置卫星的村庄可以相互通信，铺设线路的村庄也可以相互通讯。卫星的分配是不受限制的。
??? 问怎样合理的分配卫星和铺设线路，使得任意两个村庄都能直接或间接通信，并且铺设线路最短，求最短的线路是多少。n,k<=5000
??? 解：如果不设卫星，就相当于求原图的最小生成树。如何改造该模型？增设一个点v0，和所有村庄相连，权值为0，该图的一个最小生成树就对应着一种方案，铺设路线长度为对应的生成树的权值之和，生成树中与v0相关的村庄为安放卫星的村庄。这样问题转化为求dT(v0)==k的最小生成树问题了。
?
2. POJ1639
??? 题意：一些人准备去公园开party，每个人可以开车直接去或者把车开到a家，然后做a的车到公园，每辆车可以座无数个人，但公园最多只能停放k辆车。问所有人开车的路程之和最短为多少。
??? 解：把公园点v0看成度限制条件，求所有<=k的度限制生成树，取最小值即可。
/*最小度限制生成树*/#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int INF = 0x7fffffff;const int N = 30;int n,S,k; //节点总数 有度数限制的点v0 度数限制为kint mst; //最终结果：最小k限制度生成树int mp[N][N]; //图int father[N]; //节点n的父节点bool edge[N][N]; //判断边(i,j)是否加入到生成树中int best[N]; //从v0到v路径上与v0无关的最大权边的点序号char str[N][12];int dis[N];bool mark[N];bool vis[N];int pre[N];void dfs(int now){ for(int i = 0; i < n; i++) { if(edge[i][now] && mark[i]) { father[i] = now; mark[i] = false; dfs(i); } }}int prim(int s) //从点s开始的最小生成树{ int i,Min,key; int sum = 0; memset(pre,0,sizeof(pre)); memset(mark,0,sizeof(mark)); mark[s] = true; vis[s] = true; for(i = 0; i < n; i++) { dis[i] = mp[s][i]; pre[i] = s; } while(true) { Min = INF; for(i = 0; i < n; i++) { if(!vis[i] && !mark[i] && dis[i] < Min) { Min = dis[i]; key = i; } } if(Min == INF) break; mark[key] = true; vis[key] = true; edge[pre[key]][key] = edge[key][pre[key]] = true; sum += Min; for(i = 0; i < n; i++) { if(!vis[i] && !mark[i] && dis[i] > mp[key][i]) { dis[i] = mp[key][i]; pre[i] = key; } } } Min = INF; int root = -1; //找到与v0相关联的点的最小边 for(i = 0; i < n; i++) { if(mark[i] && mp[i][S] < Min) { Min = mp[i][S]; root = i; } } mark[root] = false; dfs(root); // 将树拉成有根树 father[root] = S; return sum + Min;}int Best(int x) //记忆化搜索s到x的最大权值的边{ int tmpt; if(father[x] == S) return -1; if(best[x] != -1) return best[x]; tmpt = Best(father[x]); if(tmpt != -1 && mp[tmpt][father[tmpt]] > mp[father[x]][x]) best[x] = tmpt; else best[x] = x; return best[x];}int find(char *c){ for(int i = 0; i < n; i++) { if(strcmp(str[i],c) == 0) return i; } return -1;}void input(){ int i,j; int m; int w; char s1[N],s2[N]; for(i = 0; i <= N-2; i++) for(j = 0; j <= N-2; j++) mp[i][j] = INF; scanf("%d",&m); n = 0; strcpy(str[n++],"Park"); S = 0; for(i = 0; i < m; i++) { scanf("%s %s %d",s1,s2,&w); int x = find(s1); if(x == -1) { x = n; strcpy(str[n++],s1); } int y = find(s2); if(y == -1) { y = n; strcpy(str[n++],s2); } if(w < mp[x][y]) //可能有重边 mp[x][y] = mp[y][x] = w; } scanf("%d",&k);}void solve(){ int i,j; memset(vis,0,sizeof(vis)); memset(edge,0,sizeof(edge)); memset(father,-1,sizeof(father)); vis[S] = true; int m = 0; mst = 0; //先求m度限制最小生成树 for(i = 0; i < n; i++) { if(!vis[i]) { m++; mst += prim(i); } } int change; // 回路上权值最大的边，用于交换 int ax,bx,tmp; for(i = m+1; i <= k && i < n; i++) { memset(best,-1,sizeof(best)); for(j = 0; j < n; j++) { if(best[j] == -1 && father[j] != S) Best(j); } int minadd = INF; // 交换边的最小差值 for(j = 0; j < n; j++) { if(mp[S][j]!= INF && father[j] != S) { ax = best[j]; bx = father[ax]; tmp = mp[S][j] - mp[ax][bx]; if(tmp < minadd) { minadd = tmp; change = j; } } } if (minadd >= 0) break; //用于度数不大于k的限制，如果k限制，就不用break了 mst += minadd; ax = best[change]; bx = father[ax]; mp[ax][bx] = mp[bx][ax] = INF; father[ax] = bx = S; // 改变生成树，将点ax直接指向源点S mp[ax][S] = mp[S][ax] = mp[change][S]; mp[S][change] = mp[change][S] = INF; }}int main(){ input(); solve(); printf("Total miles driven: %d\n", mst); return 0;}?
?