POJ 1637 Sightseeing tour(混合图的欧拉回路:网络流)

题目大意

给定一副 $n$ 个点, $m$ 条边的混合图(既有有向边,又有无向边),问是否存在欧拉回路。
$( 1 \leq n \leq 200, 1 \leq m \leq 1000)$

知识扩展

若图G中存在这样一条路径,使得它恰通过G中每条边一次,则称该路径为欧拉路径
若该路径是一个圈,则称为欧拉回路

具有欧拉回路的图称为欧拉图(简称E图)。

无向图存在欧拉路径/回路的充要条件:
一个无向连通图图存在欧拉路径,当且仅当有且仅有2个度数为奇数的点。特别地,当所有点的度数都为偶数时,则称为欧拉回路。

有向图存在欧拉路径/回路的充要条件:
一个有向连通图存在欧拉路径,当且仅当除了2个点外,其余的点入度等于出度,且在这2个点中,一个点的入度比出度大1,另一个点的出度比入度大1。特别地,当所有点的入度等于出度时,则称为欧拉回路。

解题思路

网络流

要判断一个混合图是否存在欧拉路径,首先得把混合图转化为有向图,也即给无向边定向。

随便定向,再判断其是否满足有向图存在欧拉回路的先决条件,也即是否所有点的入度等于出度。由于是随便定向,直接这样判断肯定是错误的,但可以发现,无论怎么定向,一个点的总度数是不会变的,而由入度等于出度可以推出每个点的度数(入度+出度)必是偶数。所以我们通过这个可以先排除掉一些不可能的图。

Ps: 有些人是通过 入度-出度=偶数 来判断的,也是可以的,道理相通。

然后就可以通过网络流建模来帮助我们找出一种正确的定向方案。

设一个点的权值为(入度-出度)/2,也即该点需要改变方向的边数。我们把图转为二分图,$X$ 集合是出度大于入度的点,$Y$ 集合是入度大于出度的点。然后从源点 $s$ 向 $X$ 集合中的点建边(容量为点权),从 $Y$ 集合中的点向汇点 $t$ 建边(容量为点权)。

至于出度等于入度的点,由于不需要调整,可以选择不加入图(若加入也相当于“中间点”,不会有影响)。

之后再把之前暂时定向的无向边加到图中去(以有向边的形式,在 $X$ 集合与 $Y$ 集合之间),且容量为1。原来的有向边由于无法改变方向,所以直接删除。

最后直接跑最大流判断是否满流就可以了。

Ps: 若有要求输出路径,可将 $X$ 集合与 $Y$ 集合之间流量为1的边反向输出。

网络流建模的原理: $X$ 集合中的点每流出一个流量单位,意味着这条边可以通过在原图中反向定向来使得该点的入出度更趋于相等(一个增加1度,一个减少1度,差值缩小了2度,这也是建图时点权需要除以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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 2e2 + 10;
const int MAXM = 1e3 + 10;
const int INF = 0x3f3f3f3f;

struct edge {
int to, cap, next;
edge( int to = 0, int cap = 0, int next = 0 ) : to(to), cap(cap), next(next) {}
} G[MAXM << 2];
int n, m;
int tot, head[MAXN], cur[MAXN];
int ou[MAXN], in[MAXN];
bool maze[MAXN][MAXN];
int d[MAXN];

bool bfs(int s, int t)
{

memset(d, -1, sizeof(d));
queue<int> que;
que.push(s);
d[s] = 0;
while( !que.empty() )
{
int u = que.front(); que.pop();
for( int i = head[u]; ~i; i = G[i].next )
{
edge e = G[i];
if( e.cap > 0 && d[e.to] == -1 )
{
d[e.to] = d[u] + 1;
que.push(e.to);
}
}
}
return ~d[t];
}
int dfs(int u, int t, int f)
{

if( u == t ) return f;
int res = 0;
for( int &i = cur[u]; ~i; i = G[i].next )
{
edge &e = G[i];
if( e.cap > 0 && d[e.to] == d[u] + 1 )
{
int tmp = dfs(e.to, t, min(e.cap, f));
if( tmp > 0 )
{
res += tmp;
f -= tmp;
e.cap -= tmp;
G[i ^ 1].cap += tmp;
if( !f ) break;
}
}
}
return res;
}
int Dinic(int s, int t)
{

int flow = 0;
while( bfs(s, t) )
{
memcpy(cur, head, sizeof(head));
int tmp;
while( tmp = dfs(s, t, INF) ) flow += tmp;
}
return flow;
}
void add_edge(int u, int v, int cap)
{

G[tot] = edge(v, cap, head[u]);
head[u] = tot++;
G[tot] = edge(u, 0, head[v]);
head[v] = tot++;
}
void init()
{

tot = 0;
memset(head, -1, sizeof(head));
memset(ou, 0, sizeof(ou));
memset(in, 0, sizeof(in));
memset(maze, 0, sizeof(maze));
}
int main()
{

int T;
scanf("%d", &T);
while( T-- )
{
init();
scanf("%d %d", &n, &m);
int u, v, o;
for( int i = 0; i < m; ++ i )
{
scanf("%d %d %d", &u, &v, &o);
ou[u]++;
in[v]++;
if( !o )
{
add_edge(u, v, 1);
maze[u][v] = true;
}
}
int sum = 0, s = 0, t = n + 1;
bool flag = true;
for( int i = 1; i <= n; ++ i )
{
if( (ou[i] + in[i]) & 1 ) flag = false;
if( ou[i] > in[i] ) sum += (ou[i] - in[i]) >> 1;
}
if( flag )
{
for( int i = 1; i <= n; ++ i )
{
if( ou[i] > in[i] ) add_edge(s, i, (ou[i] - in[i]) >> 1);
else if( ou[i] < in[i] ) add_edge(i, t, (in[i] - ou[i]) >> 1);
}
int flow = Dinic(s, t);
if( sum != flow ) flag = false;
}
if( flag ) puts("possible");
else puts("impossible");
}

return 0;
}

个人体会

重要的不是记住混合图的欧拉路径怎么求,而是要理解网络流在这里的妙用,才能真正触类旁通,举一反三。

Brain Power

若题目要求判断的是 是否存在欧拉路径 。那又该怎么做呢?

如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!