本文共 5774 字，大约阅读时间需要 19 分钟。
链接：
题目：
| Time Limit: 5000MS | | Memory Limit: 10000K |
| Total Submissions: 7780 | | Accepted: 2726 |
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
10Alphonzo Bernardo 32Alphonzo Park 57Alphonzo Eduardo 43Bernardo Park 19Bernardo Clemenzi 82Clemenzi Park 65Clemenzi Herb 90Clemenzi Eduardo 109Park Herb 24Herb Eduardo 793
Sample Output
Total miles driven: 183
Source
题目大意：
马戏团的小丑们有一个特异功能，无论一个车子有多小，他们都能钻进去，也就是说，一辆车子能够容纳无限个小丑。
现在小丑们要去一个公园野餐，他们住在不同的地方，为了节约路费（石油），要使得所有车子加起来走的路程最小，那么，小丑A
可以直接开车到公园，或者开到小丑B家，然后把车停在B家，搭B的车一起去公园。
小丑家的停车位是有限制的，但是公园的停车位是有限制的，公园最多只能停k辆车。一旦某个小丑开车到了公园，那么就必须停在公园，不能在回去载其他小丑了。
求所有小丑开车的最短总路程。
分析与总结：
最小生成树的拓展问题，经典的最小度限制生成树问题。
从昨晚搞到了现在，思想比较容易理解，但是代码实现起来比较复杂，而且还不是独立完成的。
参考资料：
1.这个ppt真心不错，看了基本上懂了：
2.IOI2004国家集训队论文--王汀《最小生成树问题的扩展》
3.黑书, P300~303，比较难懂
4.代码参考：
代码：
/*******************************************最小度限制生成树算法框架： 1. 先求出最小m度限制生成树； 2. 由最小m度限制生成树得到最小m+1度限制生成树; 3. 当dT(v0)=k时停止(即当V0的度为k的时候停止)；********************************************/#include #include #include #include
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