最小度限制生成树

    在一棵生成树中，某个顶点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 度数限制为k
int 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;
}