北大ACM试题库及解答1639——Picnic Planning

解题 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 ：Picnic Planning 题目来源：poj 1639 解法或类型：图论 作者：胡华嵩 　 Picnic Planning Time Limit:5S  Memory Limit:1000K Total Submit:237 Accepted:37 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 解题思路：最小度限制生成树 先求出v1，…,vn的最小生成树T，再加上与v0相关联的边。 求v0度数不超过K的最小生成树，不妨令Hi为v0的度数为i的最小生成树。则问题所求就是min{Hi,1<=i<=K},显然H1=T+{(0,x)},(0,x)时所有与v0关联的边中权值最小的。 在Hi-1上加入一条边（0，x）,得到一个环，然后再删掉环中一条不与0关联的边，设为（xa,xb）,这样就能得到一颗v0的度数为i的生成树，这样得到的生成树的权值和为cost(Hi-1)+cost(0,x)-cost(xa,xb),为了使权值最小，我们可以枚举x的值，删除时选取一条权值最大的。这样得到一颗v0的度数为i的最小生成树。 算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 ： （1） 找{v1,…,vn}所有的连通块，求出每个连通块的最小生成树Ti. （2） 在每个块中，选择v0相邻的最小边，得到Ht. Min<-Ht,V<-cost(Ht). （3） 循环i<-i+1 to k do 在Hi-1上选择“差额最小添删操作”，添加并删除一条边得到Hi,令v<-v+cost(添边)-cost(删边),若v 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 ： （1） O(n*n) （2） 没用 （3） O(k*n*n) 总共O(k*n*n). 源程序： · #include · #include · const int INF=1000000000; · struct Edge{ · int start,stop; · int weight; · }; · #define N 30 · int nn,s,num; · int graph[N][N]; · char name[30][15]; · Edge mst[N]; · bool find,use[30]; · int get(char* s) · { · for(int i=0;i>n; · num=1; · strcpy(name[0],"Park"); · for(i=0;i<25;i++) · for(j=0;j<25;j++) · graph[i][j]=INF; · for(i=0;i>name1>>name2; · x=get(name1); · y=get(name2); · cin>>graph[x][y]; · graph[y][x]=graph[x][y]; · } · nn=num; · cin>>s; · int r=prim(); · min=INF+1; · for(i=1;i=0) break; · if(temp!=-1){ · mst[temp].start=0; · mst[temp].stop=temp0; · mst[temp].weight=graph[0][temp0]; · } · use[j]=true; · r+=min; · } · cout<<"Total miles driven: "<