首页 > 代码库 > UVa10735 Euler Circuit (混合图的欧拉回路,最大流)
UVa10735 Euler Circuit (混合图的欧拉回路,最大流)
链接:http://vjudge.net/problem/UVA-10735
分析：题目保证底图联通，所以连通性就不用判断了。其次，不能把无向边转成有向边来做，因为本题中无向边只能经过一次，而拆成两条有向边之后变成了“沿着两个相反方向各经过一次”，所以本题不能拆边，而只能给边定向。首先我们给无向边任意定向，比如无向边（u，v），可以将其定向为u->v，于是u的出度和v的入度多1（在保证出入度相等的前提下，后者等价于出度少1），那我们这样随意定向以后反悔了怎么办呢？比如最后u的出度为4，入度为2，因此我们需要有将刚刚任意定向的边反向的机会，我们可以把出度看成是“物品”，先前任意定向的结果把这个“物品”交给了u，最后可能u多了这个“物品”，而和u通过刚才任意定向的边相连的结点v正好需要这个“物品”，所以我们在网络流建图时加上边（u,v,1）表示u能提供1个出度给v，相当于反悔了开始的决定将边反向了，然后哪些点需要扔掉一些出度呢？答案是out(i)>in(i)，哪些点需要一些出度呢？答案是out(i)<in(i)，将源点S向要扔掉出度的结点连一条容量为(out[i]-in[i])/2的弧，从需要出度的结点向汇点连一条容量为(in[i]-out[i])/2的弧，当且仅当源点连出去的弧全部满载整个图的所有结点出入度相等。（注意：in(i)和out(i)奇偶性不同则问题无解）。
1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 #include <queue> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 100 + 5; 9 const int INF = 1000000000; 10 11 struct Edge { 12 int from, to, cap, flow; 13 Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {} 14 }; 15 16 struct EdmondsKarp { 17 int n, m; 18 vector<Edge> edges; 19 vector<int> G[maxn]; 20 int a[maxn]; 21 int p[maxn]; 22 23 void init(int n) { 24 for (int i = 0; i < n; i++) G[i].clear(); 25 edges.clear(); 26 } 27 28 void AddEdge(int from, int to, int cap) { 29 edges.push_back(Edge(from, to, cap, 0)); 30 edges.push_back(Edge(to, from, 0, 0)); 31 m = edges.size(); 32 G[from].push_back(m - 2); 33 G[to].push_back(m - 1); 34 } 35 36 int Maxflow(int s, int t) { 37 int flow = 0; 38 for (;;) { 39 memset(a, 0, sizeof(a)); 40 queue<int> Q; 41 Q.push(s); 42 a[s] = INF; 43 while (!Q.empty()) { 44 int x = Q.front(); Q.pop(); 45 for (int i = 0; i < G[x].size(); i++) { 46 Edge& e = edges[G[x][i]]; 47 if (!a[e.to] && e.cap > e.flow) { 48 p[e.to] = G[x][i]; 49 a[e.to] = min(a[x], e.cap - e.flow); 50 Q.push(e.to); 51 } 52 } 53 if (a[t]) break; 54 } 55 if (!a[t]) break; 56 for (int u = t; u != s; u = edges[p[u]].from) { 57 edges[p[u]].flow += a[t]; 58 edges[p[u] ^ 1].flow -= a[t]; 59 } 60 flow += a[t]; 61 } 62 return flow; 63 } 64 }; 65 66 EdmondsKarp g; 67 68 const int maxm = 500 + 5; 69 70 int n, m, u[maxm], v[maxm], directed[maxm], id[maxm], diff[maxn]; 71 72 vector<int> G[maxn]; 73 vector<int> vis[maxn]; 74 vector<int> path; 75 76 void euler(int u) { 77 for (int i = 0; i < G[u].size(); i++) 78 if (!vis[u][i]) { 79 vis[u][i] = 1; 80 euler(G[u][i]); 81 path.push_back(G[u][i] + 1); 82 } 83 } 84 85 void print_answer() { 86 for (int i = 0; i < n; i++) { G[i].clear(); vis[i].clear(); } 87 for (int i = 0; i < m; i++) { 88 bool rev = false; 89 if (!directed[i] && g.edges[id[i]].flow > 0) rev = true; 90 if (!rev) { G[u[i]].push_back(v[i]); vis[u[i]].push_back(0); } 91 else { G[v[i]].push_back(u[i]); vis[v[i]].push_back(0); } 92 } 93 94 path.clear(); 95 euler(0); 96 97 printf("1"); 98 for (int i = path.size()-1; i >= 0; i--) printf(" %d", path[i]); 99 printf("\n");100 }101 102 int main() {103 int T;104 scanf("%d", &T);105 while (T--) {106 scanf("%d%d", &n, &m);107 g.init(n + 2);108 memset(diff, 0, sizeof(diff));109 for (int i = 0; i < m; i++) {110 scanf("%d%d", &u[i], &v[i]);111 u[i]--; v[i]--;112 diff[u[i]]++; diff[v[i]]--;113 char dir; while ((dir = getchar()) == ‘ ‘);114 directed[i] = (dir == ‘D‘ ? 1 : 0);115 if (dir == ‘U‘) { id[i] = g.edges.size(); g.AddEdge(u[i], v[i], 1); }116 }117 bool ok = true;118 int s = n, t = n + 1, sum = 0;119 for (int i = 0; i < n; i++) {120 if (diff[i] % 2 != 0) { ok = false; break; }121 if (diff[i] > 0) { g.AddEdge(s, i, diff[i] / 2); sum += diff[i] / 2; }122 if (diff[i] < 0) { g.AddEdge(i, t, -diff[i] / 2); }123 }124 if (!ok || sum != g.Maxflow(s, t)) { printf("No euler circuit exist\n"); }125 else print_answer();126 if (T) putchar(‘\n‘);127 }128 return 0;129 }
UVa10735 Euler Circuit (混合图的欧拉回路,最大流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。