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

本文主要是介绍习题 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;
}