最小度限制生成树

??? 在一棵生成树中，某个顶点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;}

?

?