POJ 1639 Picnic Planning （最小k度生成树）

 

Picnic Planning

Time Limit: 5000MS		Memory Limit: 10000K
Total Submissions: 8395		Accepted: 2971

Description

The Contortion Brothers are a famous set of circus clowns, known worldwide for their incredible ability to cram an unlimited number of themselves into even the smallest vehicle. During the off-season, the brothers like to get together for an Annual Contortionists Meeting at a local park. However, the brothers are not only tight with regard to cramped quarters, but with money as well, so they try to find the way to get everyone to the party which minimizes the number of miles put on everyone's cars (thus saving gas, wear and tear, etc.). To this end they are willing to cram themselves into as few cars as necessary to minimize the total number of miles put on all their cars together. This often results in many brothers driving to one brother's house, leaving all but one car there and piling into the remaining one. There is a constraint at the park, however: the parking lot at the picnic site can only hold a limited number of cars, so that must be factored into the overall miserly calculation. Also, due to an entrance fee to the park, once any brother's car arrives at the park it is there to stay; he will not drop off his passengers and then leave to pick up other brothers. Now for your average circus clan, solving this problem is a challenge, so it is left to you to write a program to solve their milage minimization problem.

Input

Input will consist of one problem instance. The first line will contain a single integer n indicating the number of highway connections between brothers or between brothers and the park. The next n lines will contain one connection per line, of the form name1 name2 dist, where name1 and name2 are either the names of two brothers or the word Park and a brother's name (in either order), and dist is the integer distance between them. These roads will all be 2-way roads, and dist will always be positive.The maximum number of brothers will be 20 and the maximumlength of any name will be 10 characters.Following these n lines will be one final line containing an integer s which specifies the number of cars which can fit in the parking lot of the picnic site. You may assume that there is a path from every brother's house to the park and that a solution exists for each problem instance.

Output

Output should consist of one line of the form 
Total miles driven: xxx 
where xxx is the total number of miles driven by all the brothers' cars.

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

East Central North America 2000

 

 

题目大意: 求解某点的度不大于K的最小限制生成树

解题思路：对于K限制生成树OI里有一篇论文写的很详细。求解过程如下：

（1）先将被限制的那个点root去掉，求剩下的点构成的图形中每一个联通子图的最小生成树，假设联通子图的个数为m个。

（2）对于每一个联通子图，选择一条最小的与点root连接的边。这样需要选择m条边与root连接才能构成整个图的一个生成树。所以K如果小于m，那么此题就是无解的。

（3）步骤(2)求出的是m度限制生成树，那么如何求度不大于K的最小限制生成树呢？我们可以先由m度限制生成树求解m+1度限制生成树，直到K度限制生成树，最后从其中选择一个值最小的限制生成树即为度不大于K的最小限制生成树。

（4）在m度限制生成树中，我们可以采用搜索的方法求就出任何一点i到点root的路径中最长的一条边并保存记录。然后对于每一条与点root连接的边且未被选择到生成树中的边进行处理，假设这条边是连接点root和点v的。那么我们可以用这条边替换掉root到点v这条路径中最长的那条边，这样枚举完每一条与点root连接的边且未被选择到生成树中的边后，得到的都是点root为m+1度限制的生成树，再从中选则一个最小的。

需要注意的是我们不能替换与点root连接的边，因为这样求出来的就不是m+1度限制了，这样求出的还是m度限制的。还有就是如果m+1度限制生成树的总权值如果大于m度限制生成树，则不用往下求了，因为后面的答案不会比当前的答案更优了

 

 

题目大意：

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

现在小丑们要去一个公园野餐，他们住在不同的地方，为了节约路费（石油），要使得所有车子加起来走的路程最小，那么，小丑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，比较难懂

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<string>

using namespace std;
    
const int VM=30;    // 点的数量
const int EM=1010;  // 边的数量
const int INF=0x3f3f3f3f;

int n,k;    // n,结点个数
int pre[VM];    // 父结点
int father[VM]; // 生成树中的父结点
bool edge[VM][VM];  // edg[i][j] = true 表示边[i,j]已在生成树中
int best[VM];   // best[i]保存V0到i之间权值最大的边
bool vis[VM];   // vis[i]表示点i是否以加入生成树
bool mark[VM];  // 用于求连通分量最小生成树的标记
int ans,w[VM][VM],dis[VM];
map<string,int> mp;

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);
        }
}

int BEST(int x,int v0){     // 记忆化搜索,求x到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];
}

int Prim(int s,int v0){     //求去掉与V0相连的边之后的连通分量的最小生成树
    memset(mark,0,sizeof(mark));
    vis[s]=mark[s]=true;
    for(int i=1;i<=n;i++){
        dis[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 || dis[j]<dis[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(dis[j]>w[u][j]){
                    dis[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;
        }
    mark[root]=0;    // 拉成有根树,即把当前这个连通分量用一条到V0权值最小的边连接起来
    DFS(root);      // 并且构成一棵树,利用father数组保存父结点
    father[root]=v0;
    return sum+MIN;
}

int 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;     // 连通分支的个数
    ans=0;          // 所求答案

    for(int i=1;i<=n;i++)   // 步骤1: 先求出m限制树 
        if(!vis[i]){
            m++;
            ans+=Prim(i,v0);
        }
        
    int minAdd,a,b,tmp;     // 步骤2: 由m限制树得到m+1限制树
    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)   //用于度数不大于k的限制，如果k限制，就不用break了
            break;
        ans+=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 ans;
}

int main(){

    //freopen("input.txt","r",stdin);

    string str1,str2;
    while(~scanf("%d",&n)){
        mp.clear();
        for(int i=1;i<VM;i++)
            for(int j=1;j<VM;j++)
                w[i][j]=INF;
        int cw,cnt=1;
        mp["Park"]=1;
        for(int i=0;i<n;i++){
            cin>>str1>>str2>>cw;
            if(mp[str1]==0)     mp[str1]=++cnt;
            if(mp[str2]==0)     mp[str2]=++cnt;
            if(w[mp[str1]][mp[str2]]>cw)    //注意可能有重复边
                w[mp[str1]][mp[str2]]=w[mp[str2]][mp[str1]]=cw;
        }
        n=cnt;
        scanf("%d",&k);
        printf("Total miles driven: %d\n",minDegreeST(1,k));
    }
    return 0;
}