习题 6-14 检查员的难题（Inspector’s Dilemma, ACM/ICPC Dhaka 2007, UVa12118)

原题链接：https://vjudge.net/problem/UVA-12118
分类：图
备注：欧拉路

分析：

• 要求每条指定边都过一次，显然与欧拉路类似
• 先得出各个点集(连通图的数目)，然后检查每个点集是否为欧拉路
• 欧拉路的条件为度数为奇数的点的数目为0或者2，连通图中度数为奇数的点个数必定为偶数个，若大于2，则需要把多余的点连起来，即加上(x-2)/2条边
• 最后把各个点集相连，即加上 点集数目-1 条边
• 注意给定边的数目为0时，直接输出0

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int maxv = 1000 + 5;
int V, E, T, du[maxv], g[maxv][maxv], fa[maxv], kase;
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main(void) {
	while (~scanf("%d %d %d", &V, &E, &T) && V) {
		if (E == 0) {
			printf("Case %d: 0\n", ++kase); continue;
		}
		memset(du, 0, sizeof(du));
		set<int>hav;
		int cnt = E;
		for (int i = 1; i <= V; i++)fa[i] = i;
		while (E--) {
			int a, b;
			scanf("%d %d", &a, &b);
			du[a]++; du[b]++;
			int x = find(a), y = find(b);
			hav.insert(a); hav.insert(b);
			if (x != y)fa[y] = x;
		}
		map<int, vector<int> >mySet;
		for (set<int>::iterator it = hav.begin(); it != hav.end(); ++it)mySet[find(*it)].push_back(*it);
		for (map<int, vector<int> >::iterator it = mySet.begin(); it != mySet.end(); ++it) {
			int x = 0;
			for (int i = 0; i < it->second.size(); i++) 
				if (du[it->second[i]] % 2)x++;
			x = max(0, (x - 2) / 2);
			cnt += x;
		}
		cnt += mySet.size() - 1;
		printf("Case %d: %d\n", ++kase, cnt * T);
	}
	return 0;
}