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