XieNaoban's Blog
0%

算法竞赛入门经典(第2版) 6-14UVa12118 - Inspector's Dilemma

发表于 更新于 分类于 ， 阅读次数： 评论次数：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

Desicription

In a country, there are a number of cities. Each pair of city is connected by a highway, bi-directional of course. A road-inspector s task is to travel through the highways (in either direction) and to check if everything is in order. Now, a road-inspector has a list of highways he must inspect. However, it might not be possible for him to travel through all the highways on his list without using other highways. He needs a constant amount of time to traverse any single highway. As you can understand, the inspector is a busy fellow does not want to waste his precious time. He needs to know the minimum possible time to complete his task. He has the liberty to start from and end with any city he likes. Please help him out.

Input

The input file has several test cases. First line of each case has three integers: \(V (1 <= V <= 1000)\), the number of cities, \(E (0 <= E <= V * (V-1) / 2)\), the number of highways the inspector needs to check and$ T (1 <= T <= 10)$, time needed to pass a single highway. Each of the next E lines contains two integers a and b \((1 <= a,b <= V, a!=b)\) meaning the inspector has to check the highway between cities a and b. The input is terminated by a case with \(V=E=T=0\). This case should not be processed.

Output

For each test case, print the serial of output followed by the minimum possible time the inspector needs to inspect all the highways on his list. Look at the output for sample input for details.

Sample

Input 

1
2
3
4
5
6
7
8
9
10
5 3 1
1 2
1 3
4 5
4 4 1
1 2
1 4
2 3
3 4
0 0 0

Output 

1
2
Case 1: 4
Case 2: 4

Key

题意：V个点每个点均可两两相连。现已连E条边，要求添加k条边使得E+k条边组成的图是个欧拉通路。求k。

思路：讲道理V不告诉你都可以，没什么用的条件。在题意里也说的很明白了，要求一个欧拉通路。E条边可组成若干张子图，每张图可能是颗复杂的树、可能是个欧拉通路、可能是个欧拉回路、也可能只是一条孤立的边、一条链。搜索子图个数用DFS即可。

我的思路是，首先把每个子图加边连成一个欧拉通路，然后把所有通路连接。 其中，若子图有大于2个奇数节点（奇数节点必为偶数）则需要额外的\((奇数节点/2-1)\)条边；若子图无奇数节点或只有2个，则无需额外边。 另外，连接n个通路需要n-1条边。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//UVa12118 - Inspector's Dilemma
//Accepted 0.070s
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
using namespace std;

int V, E, T;
int Case = 0;
map<int, vector<int> > mp;
bool vis[1010];
int num;

void DFS(int idx) {
	if (vis[idx]) return;
	vis[idx] = true;
	if (mp[idx].size() & 1) ++num;
	for (auto &e : mp[idx]) {
		DFS(e);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	while ((cin >> V >> E >> T)&&(V+E+T)) {
		memset(vis, 0, sizeof(vis));
		mp.clear();
		int u, v;
		for (int i = 0; i < E; ++i) {
			cin >> u >> v;
			mp[u].push_back(v);
			mp[v].push_back(u);
		}
		int res = -1;
		for (auto &e : mp) {
			if (vis[e.first]) continue;
			num = 0;
			DFS(e.first);
			if (num == 0) num = 2;
			res += num/2;
		}
		if (res < 0) res = 0;
		cout << "Case " << ++Case << ": " << T*(res + E) << '\n';

	}
	return 0;
}