首页 > 代码库 > UVa12118 Inspector's Dilemma (欧拉路径)
UVa12118 Inspector's Dilemma (欧拉路径)
链接：http://acm.hust.edu.cn/vjudge/problem/38518
分析：无向图计算欧拉路径。注意：构造的对象是欧拉路径，不是回路！条件：起终点度数为奇数，其它点的度数为偶数。有x个联通块，每个联通块形成链，在每个联通块上跑dfs求出奇点数，由于是链所以至少为2，最后将所有联通块的链合并，将多算的起点和终点减去2，然后一条边能消去两个奇点，所以需要额外添加的边数为（总奇点数—2)/2，因为E可以取0所以最后还要和0取max。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 7 const int maxn = 1000 + 5; 8 9 int V, E, T, vis[maxn];10 vector<int> roads[maxn];11 12 int dfs(int u) {13 if (vis[u]) return 0;14 vis[u] = 1;15 int odd_cnt = 0;16 odd_cnt += (roads[u].size() & 1);17 for (int i = 0; i < roads[u].size(); i++)18 odd_cnt += dfs(roads[u][i]);19 return odd_cnt;20 }21 22 int solve() {23 int ans = 0;24 for (int i = 1; i <= V; i++)25 if (!vis[i] && !roads[i].empty())26 ans += max(dfs(i), 2);27 return T * ((ans - 2) / 2 + E);28 }29 30 int main() {31 int kase = 0;32 while (scanf("%d%d%d", &V, &E, &T) == 3 && (V || E || T)) {33 for (int i = 1; i <= V; i++) roads[i].clear();34 memset(vis, 0, sizeof(vis));35 for (int i = 0; i < E; i++) {36 int u, v; scanf("%d%d", &u, &v);37 roads[u].push_back(v), roads[v].push_back(u);38 }39 printf("Case %d: %d\n", ++kase, solve());40 }41 return 0;42 }
UVa12118 Inspector's Dilemma (欧拉路径)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。