即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

POJ 1639 Picnic Planning

编程语言 qq_35776409 15℃ 0评论
本文目录
[隐藏]

1.Picnic Planning

Time Limit: 5000MS Memory Limit: 10000K


Total Submissions: 10561 Accepted: 3836


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

/*
strcpy(s1,s2);strcpy函数的意思是:把字符串s2中的内容
copy到s1中,连字符串结束标志也一起copy.
这样s1在内存中的存放为:ch\0;
strcmp函数是比较两个字符串的大小,返回比较的结果。
strcmp(s1,s2);
字符串1小于字符串2,strcmp函数返回一个负值;
字符串1等于字符串2,strcmp函数返回零;
字符串1大于字符串2,strcmp函数返回一个正值;
/************************************************* 
算法引入: 
最小k度限制生成树,就是指有特殊的某一点的度不能超过k时的最小生成树; 
如果T是G的一个生成树且dT(v0)=k,则称T为G的k度限制生成树; 
G中权值和最小的k度限制生成树称为G的最小k度生成树; 

算法思想: 
设特殊的那点为v0,先把v0删除,求出剩下连通图的所有最小生成树; 
假如有m棵最小生成树,那么这些生成树必定要跟v0点相连; 
也就是说这棵生成树的v0点至少是m度的; 
若m>k,条件不成立,无法找到最小k度限制生成树; 
若m<=k,则枚举m到k的所有最小生成树,即一步步将v0点的度加1,直到v0点的度为k为止; 
则v0点度从m到k的(k-m+1)棵最小生成树中最小的那棵即为答案; 

算法步骤: 
(1)先求出最小m度限制生成树: 
原图中去掉和V0相连的所有边(可以先存两个图,建议一个邻接矩阵,一个邻接表,用方便枚举边的邻接表来构造新图); 
得到m个连通分量,则这m个连通分量必须通过v0来连接; 
则在图G的所有生成树中dT(v0)>=m; 
则当k  
#include
#include
using namespace std;
const int maxn = 21;
const int MAX_EDGE_WEIGHT = 1000000000;
struct Edge{int w,sv,ev;};
Edge mstEdge[maxn-1];
int g[maxn][maxn];
int tot_Nodes,n,s;//s 为最小生成树顶点0的最大度数,n是边数
int ans,isCycle,exist[maxn];
char Nodesname[maxn][12];
int VerInd(char* name){
    int rt=0;
    while(rtstrcmp(Nodesname[rt],name)!=0) rt++;
    if(rt==tot_Nodes){
        strcpy(Nodesname[tot_Nodes],name);
        tot_Nodes++;
    }
    return rt;
}
int Mst_Prim(){
    int MST=0;
    for(int i=1;i1;i++){
        mstEdge[i].sv=1;mstEdge[i].ev=i+1;
        mstEdge[i].w=g[1][i+1];
    }
    for(int k=2;kint minw=mstEdge[k-1].w,index=k-1;
        for(int j=k;j1;j++)
            if(mstEdge[j].w1];
        mstEdge[k-1]=mstEdge[index];
        mstEdge[index]=tmp;

        int p=mstEdge[k-1].ev;
        for(int i=k;i1;i++){
            int v=mstEdge[i].ev,w=g[p][v];
            if(wreturn MST;
}
void Max_Edge_Incycle(int mv,int sv,int ev,int& maxw,int& ind){
    if(ev==mv){ isCycle=1;return ; }
    for(int i=0;i1;i++){
        if(mstEdge[i].sv!=ev&&mstEdge[i].ev!=ev)
            continue;
        if(mstEdge[i].sv==ev&&mstEdge[i].ev!=sv){
            Max_Edge_Incycle(mv,ev,mstEdge[i].ev,maxw,ind);
            if(isCycle){
                if(maxw0){
                    maxw=mstEdge[i].w;
                    ind=i;
                }
                break;
            }
        }
        else if(mstEdge[i].ev==ev&&mstEdge[i].sv!=sv){
                Max_Edge_Incycle(mv,ev,mstEdge[i].sv,maxw,ind);
                if(isCycle){
                    if(maxw0){
                        maxw=mstEdge[i].w;
                        ind=i;
                    }
                    break;
                }
            }
    }
}
void Solve(){
    ans=Mst_Prim();
    //查找最小的边(0,ev)的权值 minw
    int minw=MAX_EDGE_WEIGHT+1,ev=-1;
    for(int i=1;i0;
        if(g[0][i]0][i];
            ev=i;
        }
    }
    exist[ev]=1; ans+=minw;
    //将(0,ev)加入mstEdge中
    mstEdge[0].sv=0;mstEdge[0].ev=ev;mstEdge[0].w=minw;
    //枚举顶点0的度数等于2到s 求得最优解
    for(int degree=2;degree<=s;degree++){
        int dec=MAX_EDGE_WEIGHT+1,edgeInd=-1;
        ev=-1;
        for(int i=1;iif(exist[i]==1) continue;
            int maxw=0,ind=-1;
            isCycle=0;
            Max_Edge_Incycle(0,0,i,maxw,ind);
            if(dec>g[0][i]-maxw){
                dec=g[0][i]-maxw;
                edgeInd=ind;
                ev=i;
            }
        }
        if(dec>=0) break;
        else {
            if(edgeInd!=-1){
                mstEdge[edgeInd].sv=0;
                mstEdge[edgeInd].ev=ev;
                mstEdge[edgeInd].w=g[0][ev];
            }
            exist[ev]=1;ans+=dec;
        }
    }
}
int main(){
    char name1[12],name2[12];int dist;
    for(int i=0;ifor(int j=0;j0;
    cin>>n;
    strcpy(Nodesname[tot_Nodes],"Park");
    tot_Nodes++;
    for(int i=0;icin>>name1>>name2>>dist;
        int r1=VerInd(name1),r2=VerInd(name2);
        g[r1][r2]=g[r2][r1]=dist;
    }
    cin>>s;
    Solve();
    cout<<"Total miles driven: "<return 0;
}
/*这个题教会我 格式输出的时候能复制的一定要复制
不能复制的要仔细检查,我的“driven”少打了一个n调了一下午*/

转载请注明:CodingBlog » POJ 1639 Picnic Planning

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情