[UVA][轉換] 10805 - Cockroach Escape Networks
Cockroach Escape Networks
Time Limit: 3 seconds
|
"Bug powder dust an' mugwump jism And the wild boys runnin' 'round Interzone trippin'" |
Bill Lee shares his apartment with a group of cockroaches. The bugs are smart and have several nests inside the apartment. When they are inside one of the nests, Bill can not catch them. Some pairs of nests are connected by cockroach trails, and it takes one unit of time to run from one nest along a trail to any neighbouring nest. However, it takes a lot of the cockroaches' resources to maintain all of the trails in good condition. What they need is to destroy some of the trails, but still make sure that it is possible to run from any nest to any other nest along a sequence of trails.
There are n nests in the room, and each nest has at least n-1 cockroaches in it at any moment. In case of emergency (when Bill comes into the room and turns on the light), the roaches go into a state of panic - from every nest, n-1 roaches strat running, one to every other nest along the trails. Several roaches can run along the same trail without interfering with each other. The time it takes for the last cockroach to reach its destination is called the Emergency Response Time. The cockroaches are smart and always choose the shortest path.
Your task is, given a description of the cockroaches' network, find the set, T, of trails that need to be kept so that it is possible to reach any nest B from any nest A along a path in T. If there are multiple such sets, pick the one that has the fewest trails. If there is still a tie, pick the one that guarantees the smallest Emergency Response Time. Print that time.
Input
The first line of input gives the number of cases, N.
N test cases follow. Each one starts with a line containing
the integers n (the number of nests) and m (the number of
trails). The next m lines will give the pairs of nests that are
connected by a trail. The nests are numbered from 0 to n-1. n
is at most 25. There will be no trails from a node to itself and no
duplicate trails.
Output
For each test case, output the line "Case #x:", where x is the
number of the test case. On the next line, print the smallest possible
Emergency Response Time. Print an empty line after each test case.
| Sample Input | Sample Output |
2 4 4 0 1 1 2 2 3 3 0 5 7 0 1 1 4 0 2 1 2 1 3 4 3 2 3 |
Case #1: 3 Case #2: 2 |
Problemsetter: Igor Naverniouk
題目描述：
蟑螂有許多連通的路徑，為了加速與維護，打算將圖變成樹狀，然後當危險來臨時，逃跑要相當快速，
因此樹狀最長路徑要最小。
求最小的最長路徑為何，即生成一個最小最長路徑成本樹。
題目解法：
做一次 floyd，然後對於每一點得到最遠的兩點，然後找最遠加總中的最小即可。
但是要考慮最長路徑奇偶數，以及最長路徑的分布可能，會發現在奇數的情況下，
會有 2 條分別是奇數和偶數的最遠距離，可能會誤算而使答案多 1。
因此加入虛設點放在每條邊的中間，那麼窮舉時便不會有這種情況，使得每條邊都是偶數。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define oo 100000
using namespace std;
int g[505][505];
int main() {
int testcase;
int i, j, k, n, m;
int x, y, cases = 0;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
int N = n+m, node = n;
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++)
g[i][j] = oo;
g[i][i] = 0;
}
for(i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
g[x][node] = g[node][x] = 1;
g[y][node] = g[node][y] = 1;
node++;
}
for(k = 0; k < N; k++)
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
printf("Case #%d:\n", ++cases);
int ret = 0xffff;
for(i = 0; i < N; i++) {//center
int v[2] = {};
for(j = 0; j < n; j++) {
if(g[i][j] > v[1])
v[1] = g[i][j];
if(v[0] < v[1])
swap(v[0], v[1]);
}
ret = min(ret, v[0]+v[1]);
}
printf("%d\n\n", ret/2);
}
return 0;
}