uva 10735 Euler Circuit 混合图的欧拉回路判断以及输出路径 最大流

缘起

【1】中我们已经做了一道判定混合图的欧拉回路是否存在的题目. 但是依旧还是觉得不过瘾——我们想将欧拉路径输出出来. uva 10735 Euler Circuit

分析

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
给出一个V个点E条边的混合图（有的是有向边，有的是无向边）求出它的一条欧拉回路，如果没有输出无解信息，
输入保证忽略边的方向后图是连通的（V<=100, E<=500）

【输入】
多样例, 第一行是样例数. 每个样例开始于V和E(1 ≤ V ≤ 100 and 1 ≤ E ≤ 500） 顶点的编号从1到V
然后E行，每行指定一条边或者弧. 然后跟一个字母'U'或者'D'表明无向或者有向.

【输出】
如果存在欧拉路径，任何一条都可以, 否则输出 "No euler circuit exist"


Sample Input
2
6 8
1 3 U
1 4 U
2 4 U
2 5 D
3 4 D
4 5 U
5 6 D
5 6 U
4 4
1 2 D
1 4 D
2 3 U
3 4 U

Sample Output
1 3 4 2 5 6 5 4 1

No euler circuit exist

本题比较综合, 不仅仅要按照【1】中的最大流方法判定是否存在欧拉回路，还要跑fleury算法将有向图中的欧拉路径输出出来（【2】）。本题比较综合. 综合了图论和网络流的算法

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
//#define LOCAL
const int maxv = 105,maxe = 505, inf = 0x3f3f3f3f;
int v,e, indeg[maxv], outdeg[maxv], head[maxv], cnt, sum, ans[maxe], top, pre[maxv], flow[maxv]; // 这里ans的维度开到maxe. 妈蛋, WA到哭了
typedef pair<int, int> P; // first是点的编号, second是弧的编号
vector<P> gg[maxv]; // 明确了无向边的方向之后的有向图
typedef vector<P>::iterator vit;
struct // 弧(边)的数据结构
{
	int a,b;
	char c;
	bool used;
}edges[maxe]; 

struct Arc
{
	int from, to, nxt, cap, index; // index是此弧对应edges中的编号, 即边的编号
}g[maxe<<1];

void addArc(int from, int to, int cap, int index)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap, g[cnt].index = index;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0, g[cnt].index = index; // 网络流中的正向弧和反向弧的index是一样的(都是一条弧产生的)
	head[to]= cnt++;
}

bool ck()
{
	for (int i = 1; i<=v; i++)
	{
		if (outdeg[i]-indeg[i]&1)
		{
			return false;
		}
	}
	return true;
}

void build() // 这里添加的弧都是与源、汇连接的, Arc的index属性无意义（因为原本就不是e条边(弧)里面的东西）
{
	for (int i = 1; i<=v; i++)
	{
		if (outdeg[i]>indeg[i])
		{
			sum+=(outdeg[i]-indeg[i]>>1);
			addArc(0, i, outdeg[i]-indeg[i]>>1, 0); // 所以这里index参数统一传了0
		}
		else if (outdeg[i]<indeg[i])
		{
			addArc(i, v+1, indeg[i]-outdeg[i]>>1, 0);
		}
	}
}

void updata(int s, int t, int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int bfs(int s,int t)
{
	queue<int> q;
	q.push(s);
	memset(pre, -1, sizeof(pre));
	flow[s] = inf;
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		if (front==t)
		{
			updata(s,t,flow[t]);
			return flow[t];
		}
		for (int h = head[front],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!~pre[to] && g[h].cap>0)
			{
				pre[to] = h;
				flow[to] = min(flow[front], g[h].cap);
				q.push(to);
			}
		}
	}
	return 0;
}

int ek(int s,int t)
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t);
		if (d<=0)
		{
			return ans;
		}
		ans+=d;
	}
}

bool kk(int h)
{
	return g[h].from>=1&&g[h].from<=v && g[h].to>=1&&g[h].to<=v;
}

void rebuild()
{
	for (int h = 0,from,to,index; h<cnt; h+=2)
	{
		if (kk(h)) // 不是流网络中与源或者汇连接的弧, 即是原先的无向边选定方向之后的弧
		{
			if (g[h].cap) // 说明无向边应该选取的方向是g[h]
			{
				from = g[h].from;
				to = g[h].to;
			}
			else // 此边满载, 说明无向边应该选取的方向是g[h^1]
			{
				from = g[h^1].from;
				to = g[h^1].to;
			}
			index = g[h].index; // g[h]和 g[h^1]的index相等,随便哪个
			edges[index].a = from, edges[index].b = to; // 确定无向边的方向
			gg[from].push_back(P(to, index)); // 确定有向图gg
		}
	}
}

void dfs(int i) // fleury算法
{
	for (vit x = gg[i].begin(); x!=gg[i].end(); x++)
	{
		if (!edges[x->second].used)
		{
			edges[x->second].used = true;
			dfs(x->first);
			ans[top++] = x->second;
		}
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d", &v, &e);
		memset(head, -1, sizeof(head));
		memset(indeg, 0, sizeof(indeg));
		memset(outdeg, 0, sizeof(outdeg));
		cnt = sum = top = 0;
		for (int i = 1; i<=v; i++)
		{
			gg[i].clear();
		}
		memset(edges, 0, sizeof(edges));
		for(int i = 1; i<=e; i++)
		{
			scanf("%d%d", &edges[i].a, &edges[i].b);
			getchar();
			edges[i].c = getchar();
			if (edges[i].c=='U')
			{
				addArc(edges[i].a,edges[i].b,1, i);
			}
			else
			{
				gg[edges[i].a].push_back(P(edges[i].b, i)); // 否则就早早加入最后要跑fleury算法的有向图中去
			}
			outdeg[edges[i].a]++, indeg[edges[i].b]++;
		}
		if (!ck())
		{
			puts("No euler circuit exist");
			if (kase)
			{
				puts("");
			}
			continue;
		}
		build();
		if (ek(0, v+1)!=sum) // 跑最大流检验是否满流
		{
			puts("No euler circuit exist");
			if (kase)
			{
				puts("");
			}
			continue;
		}
		rebuild(); // 原混合图存在欧拉回路, 则根据上述最大流算法敲定的无向边的方向重构有向图, 最后要在这张有向图上跑fleury算法的.
		dfs(1); // 因为网络流算法已经确定了存在欧拉回路, 所以无所谓从哪个点开始, 就取1好了
		while(top--) // 逆序输出弧就是欧拉路径
		{
			printf("%d ",edges[ans[top]].a);
		}
		puts("1");
		if (kase)
		{
			puts("");
		}
	}
	return 0;
}

ac情况

Status Accepted
Length 4062
Lang C++11 5.3.0
Submitted 2019-09-27 08:59:18
Shared
RemoteRunId 23967122

其实我一直对写200+行算法程序能1A的人钦佩无比. 一口气200+行的算法程序能1A的确是一件很不容易的事情.

关于本题算法的解释

其实我们本身就是奔着有向图的欧拉回路去的. 所以我们必须要定下混合图中无向边的方向. 而无向边的方向怎么定呢? 因为混合图转有向图我们需要该有向图有欧拉回路. 而有向图有欧拉回路的条件在的条件根据【3】就是所有顶点的出度=入度. 但是现在出度>入度的作为源流量. 入度>出度的作为汇流量. 其实源流量和汇流量不为0的顶点就是阻碍当前有向图（所谓当前有向图，指的是无向边伊始随意定了方向，则混合图变成有向图）成为有欧拉回路的有向图的阻碍. 所以要扭转乾坤. 而扭转的唯一契机就是改变无向边的初始定向. 所以算法才仅仅将无向边变成的有向弧加入流网络，而没有将一开始的有向弧加入流网络. 而为什么是(out-in)/2? 因为你一旦反向的话, 则出度和入度的差距就是2，而不是1（因为入度少1，出度加1或者入度加1, 出度少1）, 即一旦反向, 扭转的是2而不是1. 而如果满流的话，就说明存在一种流的分配方式使得源流量可以通过扭转清零（注意，源流量和汇流量是相等的）.

参考

【1】https://yfsyfs.github.io/2019/09/26/poj-1637-Sightseeing-tour-EK-%E6%B7%B7%E5%90%88%E5%9B%BE%E7%9A%84%E6%AC%A7%E6%8B%89%E5%9B%9E%E8%B7%AF%E5%88%A4%E5%AE%9A/

【2】https://yfsyfs.github.io/2019/09/06/hihocoder-1181-%E6%AC%A7%E6%8B%89%E8%B7%AF%C2%B7%E4%BA%8C-Fleury%E7%AE%97%E6%B3%95/

【3】https://yfsyfs.github.io/2019/09/06/hdu-1878-欧拉回路-判断无向图是否存在欧拉回路/