poj 1637 Sightseeing tour EK 混合图的欧拉回路判定

缘起

【1】中我们得到了无向图、有向图的欧拉回路的判定方法. 但是本题处理的是混合图的欧拉回路的判定. poj 1637 Sightseeing tour

分析

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
给你一个混合图，要你判定是否存在欧拉回路.

【输入】
多样例. 首先是样例数. 每个样例开始于m和s，1 <= m <= 200,1 <= s <= 1000，m是点的个数, s是边的
数目， 然后是s行, 	每行三个整数， xi, yi, and di, 1 <= xi,yi <= m, 0 <= di <= 1
di=1的话就是弧，di=0就是边。你可以假设该混合图是有根的.

【输出】
输出 possible 或者  impossible

【样例输入】
4
5 8
2 1 0
1 3 0
4 1 1
1 5 0
5 4 1
3 4 0
4 2 1
2 2 0
4 4
1 2 1
2 3 0
3 4 0
1 4 1
3 3
1 2 0
2 3 0
3 2 0
3 4
1 2 0
2 3 1
1 2 0
3 2 0

【样例输出】
possible
impossible
impossible
possible

【限制】
1s

可能有人会说，这还不简单——【1】中已经告知了有向图怎么判定欧拉回路的存在性. 那只需要把此图视作有向图即可呀，然后判定每个点的入度是否等于出度就行了呀~

我只能说图森破~ 因为你把边视作两条弧是不行的~ 因为这意味着这条边会被正着过一遍又反着过一遍. 但是实际上欧拉回路要求的是仅仅过一遍这条边. 所以这种思路是不行的. 如果你不知道固定算法的话，这道题不是水题的好伐?

1
2
3
4
5
6
7
8
9
10
11
12
13
首先是对图中的无向边随意定一个方向，然后统计每个点的入度（indeg）和出度（outdeg），如果
indeg - outdeg是奇数的话，一定不存在欧拉回路；

如果所有点的入度和出度之差都是偶数，那么就开始网络流构图：
1，对于有向边，舍弃(即不参与建图)；对于无向边，就按照最开始指定的方向建权值为 1 的边；
2，对于入度小于出度的点，从源点连一条到它的边，权值为（outdeg - indeg）/2；
  出度小于入度的点，连一条它到汇点的权值为（indeg - outdeg）/2 的边；

构图完成，如果满流(因为满流的话,说明所有顶点的入度-出度都可以变成0)
即求出的最大流值 == 流入源的弧的权值之和，那么存在欧拉回路，否则不存在。

并且可以知道最后的无向边的方向是怎么定的.就是弧长是1的弧一旦是饱和弧的话,说明这条无向边的定向与
伊始不符，需要反向, 则只需要把这条无向边反向即可,如果需要求出欧拉回路,只需要跑fleury算法即可

你知道了上面的算法，本题就能a，不然就很难.

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
//#define LOCAL

const int maxm = 205, maxs = 1005, inf = 0x3f3f3f3f;
int m,s, head[maxm], cnt,indeg[maxm], outdeg[maxm],sum, pre[maxm], flow[maxm]; // sum用于判定是否满流

struct Arc
{
	int from,to, nxt,cap;
}g[maxs<<1];

void addArc(int from, int to, int cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap =cap;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap =0;
	head[to] = cnt++;
}

bool ck()
{
	for (int i = 1; i<=m;i++)
	{
		if (indeg[i]-outdeg[i]&1) // 必须都是偶数
		{
			return false;
		}
	}
	return true;
}

void build()
{
	for (int i = 1; i<=m; i++)
	{
		if (indeg[i]>outdeg[i])
		{
			addArc(i, m+1, indeg[i] - outdeg[i]>>1);
		}
		else if (outdeg[i]>indeg[i])
		{
			addArc(0, i, outdeg[i]-indeg[i]>>1);
			sum+=outdeg[i]-indeg[i]>>1; // 计算流量,最后和最大流判断一下是否相等来判断是否存在欧拉回路
		}
	}
}

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;
	memset(pre, -1, sizeof(pre));
	q.push(s);
	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;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\ac.out", "w", stdout);
#endif
	int n;
	scanf("%d", &n);
	while (n--)
	{
		memset(head, -1,sizeof(head));
		memset(indeg, 0, sizeof(indeg));
		memset(outdeg, 0,sizeof(outdeg));
		cnt = sum = 0;
		scanf("%d%d", &m,&s);
		while(s--)
		{
			int x,y,d;
			scanf("%d%d%d", &x, &y, &d);
			if (!d) // 有向弧不参与建图
			{
				addArc(x,y,1); // 无向边就选x->y的方向, 注意, 有可能存在重边, 则应该按照 poj 1459 Power Network 那题的思想进行加速的,但是本题s较小, 不需要
			}
			outdeg[x]++, indeg[y]++; // 但是弧和边都需要更新indeg和outdeg
		}
		if (!ck())
		{
			puts("impossible");
			continue;
		} // 如果有出度-入度不为偶数的话, 则一定不存在欧拉回路
		build(); // 建图, 0为源, m+1为汇
		ek(0,m+1)==sum?puts("possible"):puts("impossible"); // 跑最大流算法判定是否存在欧拉回路
	}
	return 0;
}

ac情况

Status Accepted
Time 47ms
Memory 564kB
Length 2397
Lang G++
Submitted 2019-09-26 16:26:00
RemoteRunId 20900405

参考

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