poj 1639 Picnic Planning(最小渡限制生成树)

链接：

http://poj.org/problem?id=1639

题目：

Description

Input

Output

Sample Input

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

Sample Output

Total miles driven: 183

Source

题目大意：

马戏团的小丑们有一个特异功能，无论一个车子有多小，他们都能钻进去，也就是说，一辆车子能够容纳无限个小丑。

现在小丑们要去一个公园野餐，他们住在不同的地方，为了节约路费（石油），要使得所有车子加起来走的路程最小，那么，小丑A

可以直接开车到公园，或者开到小丑B家，然后把车停在B家，搭B的车一起去公园。

小丑家的停车位是有限制的，但是公园的停车位是有限制的，公园最多只能停k辆车。一旦某个小丑开车到了公园，那么就必须停在公园，不能在回去载其他小丑了。

求所有小丑开车的最短总路程。

分析与总结：

最小生成树的拓展问题，经典的最小度限制生成树问题。

从昨晚搞到了现在，思想比较容易理解，但是代码实现起来比较复杂，而且还不是独立完成的。

参考资料：

1.这个ppt真心不错，看了基本上懂了：

     http://wenku.baidu.com/view/70ef0e00eff9aef8941e06db.html

2.IOI2004国家集训队论文--王汀《最小生成树问题的扩展》

    http://wenku.baidu.com/view/41800d66ddccda38376bafac.html

3.黑书, P300~303，比较难懂

4.代码参考：

    http://www.cnblogs.com/ylfdrib/archive/2010/08/21/1805505.html

代码：

/*******************************************
最小度限制生成树
算法框架：
    1. 先求出最小m度限制生成树；
    2. 由最小m度限制生成树得到最小m+1度限制生成树;
    3. 当dT(v0)=k时停止(即当V0的度为k的时候停止)；

********************************************/

#include<algorithm>
#include<iostream>
#include<string>
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;

map<string, int>mp;

const int VN  = 30;    // 点的数量
const int EN  = VN*VN; // 边的数量
const int INF = 0x7fffffff;
int limit;

template<typename Type>
class Prim{
public:
    void init(int _n){
        for(int i=1; i<VN-1; ++i){
            w[i][i] = INF;
            for(int j=i+1; j<VN; ++j)
                w[i][j]=w[j][i]=INF;
        }
    }
    void setVertexNum(int x){
        n = x;
    }
    void insert(int u, int v, Type weight){
        if(w[u][v]>weight) w[u][v] = weight; //注意可能有重复边
    }
    Type minDegreeST(int v0, int k){ // v0是限制度的点， k是限制的度数
        memset(father, -1, sizeof(father));
        memset(vis, 0, sizeof(vis));
        memset(edge, 0, sizeof(edge));
        vis[v0] = true;
        int m = 0;  // 连通分支的个数
        mst = 0;         // 所求答案

        /* 步骤1: 先求出m限制树 */
        for(int i=1; i<=n; ++i)if(!vis[i]){
            ++m;
            mst += prim(i, v0);
        }
        /* 步骤2: 由m限制树得到m+1限制树 */
        int minAdd, a, b, tmp;
        int change;  // 回路上权值最大的边，用于交换
        for(int i=m+1; i<=k&&i<=n; ++i){
            memset(best, -1, sizeof(best));
            for(int j=1; j<=n; ++j)if(best[j]==-1 && father[j]!=v0){
                Best(j, v0);
            } 
            minAdd = INF;
            for(int j=1; j<=n; ++j)if(w[v0][j]!=INF && father[j]!=v0){ //遍历所有边
                a = best[j];
                b = father[best[j]];
                tmp = w[v0][j] - w[a][b];
                if(tmp < minAdd){
                    minAdd=tmp;
                    change = j;
                }
            }
            if(minAdd >= 0) break; //用于度数不大于k的限制，如果k限制，就不用break了
            mst += minAdd;
            a = best[change];
            b = father[change];
            w[a][b] = w[b][a] = INF;
            father[a] = b = v0;
            w[a][b] = w[b][a] = w[change][v0];
            w[v0][change] = w[change][v0] = INF;
        } 
        return mst;

    }
   
private:
    // 拉成有根树
    void dfs(int cur){
        for(int i=1; i<=n; ++i)if(mark[i] && edge[i][cur]){
            father[i] = cur;
            mark[i] = 0;
            dfs(i);
        }
    }
    // 记忆化搜索,求x到V0路径上权值最大的边
    int Best(int x, int V0){
        if(father[x]==V0) return -1;
        if(best[x] != -1){
            return best[x];
        }
        int tmp = Best(father[x], V0);
        if(tmp!=-1 && w[tmp][father[tmp]] > w[father[x]][x])
            best[x] = tmp;
        else
            best[x] = x;
        return best[x];
    }
    /* 求去掉与V0相连的边之后的连通分量的最小生成树 */
    Type prim(int s, int V0){
        memset(mark, false, sizeof(mark));
        vis[s] = mark[s] = true;
        for(int i=1; i<=n; ++i){
            key[i] = w[s][i]; pre[i] = s; 
        }
        int sum=0;
        for(int i=1; i<n; ++i){
            int u=-1;
            for(int j=1; j<=n; ++j)if(!vis[j]&&!mark[j]){
                if(u==-1||key[j]<key[u]) u=j;
            }
            if(u==-1) break;
            vis[u] = mark[u] = true;
            edge[pre[u]][u] = edge[u][pre[u]] = true;
            sum += w[pre[u]][u];
            for(int j=1; j<=n; ++j)if(!vis[j]&&!mark[j]){
                if(key[j]>w[u][j]){
                    key[j] = w[u][j]; pre[j] = u;
                }
            }
        }
        int Min = INF;
        int root = -1;  // 树根
        for(int i=1; i<=n; ++i)if(mark[i] && w[i][V0]<Min){
            Min = w[i][V0];
            root = i;
        }
        // 拉成有根树,即把当前这个连通分量用一条到V0权值最小的边连接起来
        // 并且构成一棵树,利用father数组保存父结点
        mark[root] = 0;
        dfs(root);
        father[root] = V0;
        return sum + Min;
    }

private:
    int n;             // 结点个数
    int pre[VN];       // 父结点 
    int father[VN];    // 生成树中的父结点
    bool edge[VN][VN]; // edg[i][j] = true 表示边[i,j]已在生成树中
    int best[VN];      // best[i]保存V0到i之间权值最大的边
    bool vis[VN];      // vis[i]表示点i是否以加入生成树
    bool mark[VN];     // 用于求连通分量最小生成树的标记
    Type mst;          // 保存答案 
    Type w[VN][VN], key[VN];

};
Prim<int>G;
  

int main(){
    int n, d, a, b;
    string name1,name2;
    mp["Park"] = 1;
    scanf("%d",&n);
    G.init(n);
    int cnt=1;
    for(int i=0; i<n; ++i){
        cin >> name1 >> name2 >> d;
        a=mp[name1];  b=mp[name2];
        if(!a)a=mp[name1]=++cnt;
        if(!b)b=mp[name2]=++cnt;
        G.insert(a,b,d);
        G.insert(b,a,d);
    }
    G.setVertexNum(cnt);
    scanf("%d",&limit);
    printf("Total miles driven: %d\n", G.minDegreeST(1, limit));
    return 0;
}

——  生命的意义，在于赋予它意义。

          
     原创 http://blog.csdn.net/shuangde800 ， By   D_Double  (转载请标明)