PKU 1639 Picnic Planning解题报告
分类：
图论、最小度限制生成树
原题：
Picnic Planning
|
Time Limit: 5000MS
|
|
Memory Limit: 10000K
|
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
题目大意：
一些人想从各自的家中开车到一个地方野餐，每个人的家中都可以容纳无限多的车子，每个人的车子可以容纳无限多的人。每个人可以先开车到另一人家中，将车停在那人家中，两人（或多人）再开同一辆车开往目的地。但野餐的地方只有有限个停车位k，告诉你一些路程的长度，问你将所有人都聚集再野餐地点，所使用的最短路程是多少。
思路：
因为题目中说到，一个人可以先开车到其他人家中，然后他们再一起开车前往目的地，所以将问题抽象出来，将各人的家和目的地看作点，将各个路程看作边，若没有目的地停车位（点的度）的限制，问题就可以转化为求最小生成树的问题。但加上了对某一点度的限制，问题就变得复杂了。
假设，若我们将度限制条件放在一边，直接求最小生成树。如果在最小生成树中，目的地所在点的度数已经满足degree <= k，那么度限制生成树就已经得到了。因为不可能有比它权值和更小的生成树了，并且点的度数满足条件。
还有一种情况，那就是先按最小生成树算法得到的生成树中，目的地所在点的度数degree > k，那么很自然的，我们就要想到删去degree-k条树中与规定点相连的边，使得它满足度限制要求。每删去边之后，都要再加上一条边，否则图就会不连通，但是，又应该怎样删边呢？假设，规定点的度数为t，那么就有t根与规定点相连的子树T1、T2、……、Tt，若删去Ti与规定点相连的那条边，Ti这棵子树就“悬空”了，必须将Ti这棵树“架”到其他子树上才可以。经过这样一次的“删添”操作之后，修改之后的图仍然是棵树，但规定点的度数减少了1，只要这样进行t-k次，就可以得到满足条件的度限制生成树了。但怎样保证最小呢？只要在每次的“删添”操作时，保证“添”的边的权值减去“删”的边的权值的差值（必大于等于0）最小就可以了。
除了这种方法，lrj的书上还介绍了另一种方法。其大致思想是：现将规定点以及与它相连的边都去掉，再在剩下的图中求出每个连通分量的最小生成树，在进行“差额最小添删操作”，求出满足度限制的情况下的可能的权值，在其中不断更新树的权值和。具体算法将黑书P300~P303。
代码：
#include <iostream>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 50;
struct Edge
{
int
a, b;
int
len;
};
vector<Edge> edge;
map<string, int> nameIndex;
int G[MAX][MAX];
int tree[MAX][MAX];
int n, m, k;
int parkIndex;
int degree[MAX];
int treeDegree[MAX];
int p[MAX];
int inTree[MAX];
int rank[MAX];
int minCost;
int treeTag[MAX]; //对子树进行标记
int visited[MAX];
int subTreeNum;
bool operator< (Edge e1, Edge e2)
{
return
( e1.len < e2.len );
}
void Input ()
{
string
a, b;
int
index1, index2;
int
len;
Edge
e;
n
= 0;
cin>>m;
for
(int i=0; i<m; i++)
{
cin>>a>>b>>len;
if
( nameIndex.find(a) == nameIndex.end() )
{
nameIndex[a]
= n;
index1
= n;
n
++;
}
else
{
index1
= nameIndex[a];
}
if
( nameIndex.find(b) == nameIndex.end() )
{
nameIndex[b]
= n;
index2
= n;
n
++;
}
else
{
index2
= nameIndex[b];
}
if
( a == "Park" )
parkIndex
= index1;
if
( b == "Park" )
parkIndex
= index2;
G[index1][index2]
= G[index2][index1] = len;
e.a
= index1;
e.b
= index2;
e.len
= len;
edge.push_back(e);
degree[index1]
++;
degree[index2]
++;
}
cin>>k;
}
int Find (int x)
{
int t, root, w;
t
= x;
while ( p[t] != -1 )
t
= p[t];
root = t;
t
= x;
while ( p[t] != -1 )
{
w
= p[t];
p[t]
= root;
t
= w;
}
return root;
}
void Union (int x, int y)
{
int
r1, r2;
r1
= Find(x);
r2
= Find(y);
if
( rank[r1] >= rank[r2] )
{
p[r2]
= r1;
if
( rank[r1] == rank[r2] )
rank[r1]++;
}
else
p[r1]
= r2;
}
bool Kruskal ()
{
int
i, r1, r2, k, total, Max;
memset(p,
-1, sizeof(p));
memset(inTree,
0, sizeof(inTree));
memset(rank,
1, sizeof(rank));
//qsort(edge,
edgeNum, sizeof(edge[0]), cmp);
sort(edge.begin(),
edge.end());
Max = -1;
k
= 0;
minCost
= 0;
for
(i=0; i<edge.size() && k<n-1; i++)
{
r1
= Find(edge[i].a);
r2
= Find(edge[i].b);
if
( r1 != r2 )
{
tree[edge[i].a][edge[i].b]
= tree[edge[i].b][edge[i].a] = edge[i].len;
//cout<<edge[i].a<<'
'<<edge[i].b<<endl;
Union(r1,
r2);
inTree[i]
= 1;
treeDegree[edge[i].a]
++;
treeDegree[edge[i].b]
++;
k++;
minCost
+= edge[i].len;
}
}
if
( k == n - 1 )
return true;
else
return
false;
}
void DFS (int cur, int index)
{
visited[cur]
= 1;
treeTag[cur]
= index;
int
i;
for
(i=0; i<n; i++)
{
if
( tree[cur][i] && !visited[i] )
{
DFS
(i, index);
}
}
}
void MakeTreeTag ()
{
int
i;
subTreeNum
= 0;
memset(visited,
0, sizeof(visited));
visited[parkIndex]
= 1;
memset(treeTag,
-1, sizeof(treeTag));
for
(i=0; i<n; i++)
{
if
( tree[parkIndex][i] )
DFS
(i, subTreeNum++);
}
}
//将原来的子树架在另一棵树上
void ChangeTreeTag (int pre, int cur)
{
int
i;
for
(i=0; i<n; i++)
if
( treeTag[i] == pre )
treeTag[i]
= cur;
}
//从当前子树查找与其他子树相连的最小边
Edge FindMinEdge (int curTag)
{
int
i;
Edge
e;
e.len
= -1;
for
(i=0; i<edge.size(); i++)
{
if
( ((treeTag[edge[i].a] == curTag && treeTag[edge[i].b] != curTag
&& edge[i].b != parkIndex)
||
(treeTag[edge[i].b] == curTag && treeTag[edge[i].a] != curTag
&& edge[i].a != parkIndex) )
&&
G[edge[i].a][edge[i].b] )
{
if
( e.len == -1 || edge[i].len < e.len )
{
e.a
= edge[i].a;
e.b
= edge[i].b;
e.len
= edge[i].len;
}
}
}
return
e;
}
void DeleteAdd ()
{
int
i, minDif, delTag, newTag;
minDif
= -1;
Edge
addEdge, delEdge, temp;
for
(i=0; i<n; i++)
{
if
( i == parkIndex )
continue;
temp
= FindMinEdge(treeTag[i]);
if
( temp.len == -1 )
continue;
if
( tree[parkIndex][i] && ( minDif == -1 || temp.len - tree[parkIndex][i]
< minDif) )
{
minDif
= temp.len - tree[parkIndex][i];
addEdge
= temp;
delEdge.a
= parkIndex;
delEdge.b
= i;
delTag
= treeTag[i];
if
( treeTag[addEdge.a] != delTag )
newTag
= treeTag[addEdge.a];
else
newTag
= treeTag[addEdge.b];
}
}
tree[delEdge.a][delEdge.b]
= tree[delEdge.b][delEdge.a] = 0;
G[delEdge.a][delEdge.b]
= G[delEdge.b][delEdge.a] = 0;
tree[addEdge.a][addEdge.b]
= tree[addEdge.b][addEdge.a] = addEdge.len;
minCost
+= minDif;
ChangeTreeTag(delTag,
newTag);
}
void Solve ()
{
Kruskal();
if
( treeDegree[parkIndex] <= k )
{
cout<<"Total
miles driven: "<<minCost<<endl;
return;
}
MakeTreeTag
();
int
i;
for
(i=0; i<treeDegree[parkIndex]-k; i++)
DeleteAdd();
cout<<"Total
miles driven: "<<minCost<<endl;
}
int main ()
{
Input
();
Solve
();
return
0;
}