题意
给出若干二色珠子,问你能不能把他们重新排列以连成一条环,使得相邻的两个珠子颜色相同。
思路
转化为欧拉图问题。令结点代表不同的颜色,连接两个结点的边代表珠子。把珠子连成项链的过程转化为求出一种走法使得我们可以走完全部的边然后返回起点。这就是典型的欧拉回路问题了。
如果不会这个知识,请参考:有关欧拉图问题的一些总结。
代码
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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
// // UVa10054.cpp // playground // // Created by 張正昊 on 28/9/15. // Copyright © 2015 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXN = 55; const int MAXE = 2005; struct Graph{ int head[MAXN]; int deg[MAXN]; int nxt[MAXE]; int from[MAXE]; int end[MAXE]; int vis[MAXE]; int q; int V,E; inline void addEdge(int _from,int _to){ from[q] = _from; end[q] = _to; deg[_from]++; nxt[q] = head[_from]; head[_from] = q++; } inline void clear(){ q = 2; memset(head, 0, sizeof(head)); memset(nxt, 0, sizeof(nxt)); memset(end, 0, sizeof(end)); memset(vis, false, sizeof(vis)); memset(from, 0, sizeof(from)); memset(deg, 0, sizeof(deg)); } }; stack<int> res; void euler_dfs(Graph &g,int cur){ for (int i = g.head[cur]; i; i = g.nxt[i]) { if (!g.vis[i]) { g.vis[i] = true; g.vis[i^1] = true; euler_dfs(g,g.end[i]); res.push(i); } } } vector<int> singular; int euler_judge(Graph &g){ singular.clear(); for (int i = 1; i <= g.V; i++) { if (g.deg[i] % 2) { singular.push_back(i); } } if(singular.size() == 0){ for (int i = 1; i<= g.V; i++) { if (g.deg[i]) { singular.push_back(i); break; } } return 1;//euler loop }else{ return 0;//failed } } Graph gph; int main(){ int caseCnt; scanf(" %d",&caseCnt); for (int d = 1; d <= caseCnt; d++) { int n; scanf(" %d",&n); gph.clear(); gph.V = 50; gph.E = n; for (int i = 1; i<= n; i++) { int a,b; scanf(" %d %d",&a,&b); gph.addEdge(a, b); gph.addEdge(b, a); } printf("Case #%d\n",d); if (euler_judge(gph)) { euler_dfs(gph,singular[0]); if (res.size() != n) { while (!res.empty()) { res.pop(); } printf("some beads may be lost\n"); }else{ while (!res.empty()) { printf("%d %d\n",gph.from[res.top()],gph.end[res.top()]); res.pop(); } } }else{ printf("some beads may be lost\n"); } if(d != caseCnt){ puts(""); } } return 0; } |
October 31, 2015
[…] 详细题解与AC代码:请点按此处 […]