[UVA][MST&窮舉] 1040 - The Traveling Judges Problem
A group of judges must get together to judge a contest held in a particular city, and they need to figure out the cheapest way of renting cars in order to get everyone to the contest. They observed that it might be cheaper if several judges share a rental car during all or part of the trip, thus reducing the overall cost. Your task is to identify the routes the judges should take in order to minimize the total cost of their car rentals.
We will make the following assumptions:
- The cost of a rental car is proportional to the distance it is driven. There are no charges for more than one occupant in the car, fuel, insurance, or leaving the car in a city other than that in which it was rented.
- All rental cars are billed at the same rate per mile.
- A rental car can accommodate any number of passengers.
- At most one road directly connects any pair of cities. Each road is two-way and has an integer length greater than zero.
- There is at least one route from every judge's starting city to the city in which the contest is held.
- All judges whose routes to the contest take them from or through the same city travel from that city to the contest together. (A judge might arrive at a city in one car and leave that city in a different car.)
Input
The input contains several test cases. Each test case includes a route map, the destination city where the contest is being held, and the cities where the judges are initially located.
Each case appears in the input as a list of integers separated by blanks and/or ends of lines. The order and
interpretation of the integers in each case is as follows:
- NC-the number of cities that appear in the route map; this will be no larger than 20.
- DC-the number of the destination city, assuming the cities are numbered 1 to NC.
- NR-the number of roads in the route map. Each road connects a distinct pair of cities.
- For each of the NR roads, three integers C1, C2, and DIST. C1 and C2 identify two cities connected by a road, and DIST gives the distance between these cities along that road.
- NJ-the number of judges. This number will be no larger than 10.
- NJ-integers, one for each judge each of these is a city number identifying the initial location of that judge.
The data for the last case will be followed by a line consisting of the integer `-1'.
Output
For each test case, display the case number (1, 2,...) and the shortest total distance traveled by the rental cars conveying the judges to the contest. Then display the list of routes used by the judges, each route on a separate line, in the same order as the ordering of starting cities given in the input. Each route consists of the cities that the corresponding judge must visit, listed in the order in which they are visited, starting with the judge's starting city and ending with the contest city. Any other cities along the route are listed in the order in which they are visited during the judge's travels. Separate the numbers in the route with `-', and precede each route by three spaces.
If multiple sets of routes have the same minimum distance, choose a set that requires the fewest number of cities. If
several sets of cities of the same cardinality may be used, choose the set that comes lexicographically first when
ordered by city number (e.g., {2, 3, 6} rather than {2, 10, 5}). If multiple routes are still available, output any set
of routes that meets the requirements.
Follow the format of the sample output.
Sample Input
5
3 5
1 2 1
2 3 2
3 4 3
4 5 1
2 4 2
2
5
1
4
4 3
1 3 1
2 3 2
3 4 2
2
1
2
3
3 3
1 2 2
1 3 3
2 3 1
2
2
1
-1
Sample Output
Case 1: distance = 6 5-4-2-3 1-2-3 Case 2: distance = 5 1-3-4 2-3-4 Case 3: distance = 3 2-3 1-2-3
題目描述：
法官們要到某城市參加會議，他們可以共同搭車減少費用。
而每一台車可以容納無限多人，問最少花費為何，並且輸出每個法官的移動情況。
如果最少花費有多個時，找一個最少城市使用個數，再相同時，找一個字典順最小的。
如果還是有多個路徑時，任何一組都可以。
題目解法：
事實上題目要找的是並不是所有點的最小生成樹，而是要找法官們起始位置和目的地都要在樹上。
這種問題好像是 NP problem，實際的英文名稱忘了。
不過由於點很少，可以嘗試窮舉哪些點使用在樹上，再做一棵 MST。
輸出路徑時，將 MST 以目的地為 root 整理成一個有根樹即可。
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
int x, y, cost;
bool operator<(const edge &a) const {
return cost < a.cost;
}
};
vector<int> g[25];
edge E[1024];
int parent[25];
int findp(int x) {
return parent[x] == x ? x : parent[x]=findp(parent[x]);
}
int main() {
int N, D, R, NJ;
int J[25], cases = 0;
int i, j, k;
int x, y, v;
while(scanf("%d %d %d", &N, &D, &R) == 3) {
D--;
for(i = 0; i < N; i++)
g[i].clear();
for(i = 0; i < R; i++) {
scanf("%d %d %d", &x, &y, &v);
x--, y--;
g[x].push_back(y);
g[y].push_back(x);
E[i].x = x, E[i].y = y, E[i].cost = v;
}
scanf("%d", &NJ);
int must = 1<<D;
for(i = 0; i < NJ; i++) {
scanf("%d", &J[i]);
J[i]--;
must |= 1<<J[i];
}
sort(E, E+R);
// process brute force + MST
int allstate = 1<<N;
int mndist = 0xfffffff, mncity;
vector<int> rg[25];
for(i = 0; i < allstate; i++) {
if((i&must) != must)
continue;
int dist = 0, e = 0, node = 0;
vector<int> mst[25];
for(j = 0; j < N; j++) {
parent[j] = j;
node += (i>>j)&1;
}
e = node-1;
for(j = 0; j < N; j++) {
if(((i>>E[j].x)&1) && ((i>>E[j].y)&1)) {
x = findp(E[j].x);
y = findp(E[j].y);
if(x != y) {
dist += E[j].cost;
parent[x] = y;
e--;
mst[E[j].x].push_back(E[j].y);
mst[E[j].y].push_back(E[j].x);
}
}
}
if(e || dist > mndist || (dist == mndist && node > mncity))
continue;
if(mndist > dist || (mndist == dist && mncity > node)) {
mndist = dist, mncity = node;
for(j = 0; j < N; j++)
rg[j] = mst[j];
}
}
// mst -> rooted tree.
int visited[25] = {};
queue<int> Q;
Q.push(D), visited[D] = 1;
while(!Q.empty()) {
x = Q.front(), Q.pop();
for(i = 0; i < rg[x].size(); i++) {
if(visited[rg[x][i]] == 0) {
visited[rg[x][i]] = 1;
Q.push(rg[x][i]);
parent[rg[x][i]] = x;
}
}
}
printf("Case %d: distance = %d\n", ++cases, mndist);
for(i = 0; i < NJ; i++) {
printf(" %d", J[i]+1);
x = parent[J[i]];
while(x != D) {
printf("-%d", x+1);
x = parent[x];
}
printf("-%d\n", D+1);
}
puts("");
}
return 0;
}