混合图的欧拉路经
算法的步骤
- 给无向图随意的指一个方向，然后两点间加一条边，表示可以反向。
- 0节点给每一个out[i]>in[out]的节点连一条边，容量为(out[i]-in[i])/2;
- 每一个out[i]<in[out]的节点向n+1连一条边，容量为(in[i]-out[i])/2;
- 跑最大流，然后判断s连出去的点是否是满流。因为必须保证out[i] == in[i]
未验证的代码
cout和printf不要混用。。。
欧拉路径
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
using namespace std;
const int maxn = 1e3+10;
int n, m;
int in[maxn], out[maxn];
const int INF = 1e9+10;
struct Edge{
int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn];
void AddEdge(int u, int v, int cap){
edges.push_back(Edge{u, v, cap, 0});
edges.push_back(Edge{v, u, 0, 0});
int m = edges.size();
G[u].push_back(m-2);//压入边的序号
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn];
bool BFS(int s, int t){
memset(vis, 0, sizeof(vis));
queue<int> q;
memset(d, 0, sizeof(d));
d[t] = 0;
vis[t] = true;
q.push(t);
while(!q.empty()){
int temp = q.front();
q.pop();
for(int i=0; i<G[temp].size(); i++){
Edge &e = edges[G[temp][i]];
if(!vis[e.to]&&e.cap>e.flow){
vis[e.to] = true;
d[e.to] = d[temp]+1;
q.push(e.to);
}
}
}
return vis[s];
}
int p[maxn];
int num[maxn];
int cur[maxn];
int Augment(int s, int t) {
int x = t, a = INF;
while(x != s) {
Edge& e = edges[p[x]];
a = min(a, e.cap-e.flow);
x = edges[p[x]].from;
}
x = t;
while(x != s) {
edges[p[x]].flow += a;
edges[p[x]^1].flow -= a;
x = edges[p[x]].from;
}
return a;
}
int Maxflow(int s, int t) {
int flow = 0;
BFS(s, t);
memset(num, 0, sizeof(num));
for(int i = 0; i < n; i++) num[d[i]]++;
int x = s;
memset(cur, 0, sizeof(cur));
while(d[s] < n) {
if(x == t) {
flow += Augment(s, t);
x = s;
}
int ok = 0;
for(int i = cur[x]; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(e.cap > e.flow && d[x] == d[e.to] + 1) { // Advance
ok = 1;
p[e.to] = G[x][i];
cur[x] = i; // 注意
x = e.to;
break;
}
}
if(!ok) { // Retreat
int m = n-1; // 初值注意
for(int i = 0; i < G[x].size(); i++) {
Edge& e = edges[G[x][i]];
if(e.cap > e.flow) m = min(m, d[e.to]);
}
if(--num[d[x]] == 0) break;
num[d[x] = m+1]++;
cur[x] = 0; // 注意
if(x != s) x = edges[p[x]].from;
}
}
return flow;
}
void init(){
for(int i=0; i<maxn; i++)G[i].clear();
edges.clear();
memset(p, 0, sizeof(p));
memset(cur, 0, sizeof(cur));
memset(num, 0, sizeof(num));
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
init();
int u, v, w;
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>u>>v>>w;
out[u]++;
in[v]++;
if(w == 0){//w=0代表是无向边
AddEdge(u, v, 1);
}
}
bool flag = true;
for(int i=1; i<=n; i++){
if(out[i]-in[i]>0){
AddEdge(0, i, (out[i]-in[i])>>1);
}
else if(out[i]-in[i]<0){
AddEdge(i, n+1, (in[i]-out[i])>>1);
}
if(abs(out[i]-in[i])%2){
flag = false;
}
}
if(!flag){
cout<<"impossible"<<endl;
continue;
}
n = n+2;
Maxflow(0, n-1);
for(int i=0; i<G[0].size(); i++){
if(edges[G[0][i]].cap>0&&
edges[G[0][i]].cap>edges[G[0][i]].flow){
flag = false;
break;
}
}
if(!flag){
cout<<"impossible"<<endl;
}
else{
cout<<"possible"<<endl;
}
}
return 0;
}
本文标题:欧拉路径
文章作者:Babydragon
发布时间:2018-06-19, 23:46:42
最后更新:2018-06-20, 23:10:54
原始链接:http://baolintian.github.io/2018/06/19/欧拉路径/
许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。