UVA10735 混合图欧拉回路

Posted by Cww97 on 2016-10-10

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/52773071
from CAH,here
讲的比lrj还要详细,

这里写图片描述
这里写图片描述

个人的傻逼错误:
需要注意的是,网络流里是有反向边的,dinic跑完之后反向边不要添加到新图里面了

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
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF=0x3f3f3f3f;
const int N = 9999;

struct Euler
{
struct Edge{
int to,nxt;
Edge(){}
Edge(int x,int y):to(x),nxt(y){}
}edges[N];
int head[N],n,E;
inline void Init(const int &n){
this->n = n; E = 0;
for (int i=0;i<=n;i++)head[i]=-1;
}
inline void AddEdge(int f,int t){
edges[++E] = Edge(t,head[f]);
head[f] = E ;
}
stack<int >S;
bool vis[N];//use when dfs
inline void dfs(int x){//get EulerCircle
Edge e;
for (int i=head[x];i!=-1;i=e.nxt){
e = edges[i];
if (vis[i])continue;
vis[i] = 1;
dfs(e.to);
S.push(x);
}
}
inline void getEulerCircle(){
while (!S.empty())S.pop();
memset(vis,0,sizeof(vis));
dfs(1);
for (;!S.empty();S.pop()){
printf("%d ",S.top());
}
puts("1");
}
}gg;

struct Dinic
{
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):
from(u),to(v),cap(c),flow(f){}
};
int n, s, t;
vector<Edge>edges;
vector< int>G[N]; //gragh
bool vis[N]; //use when bfs
int d[N],cur[N];//dist,now edge,use in dfs
inline void AddEdge(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from, 0 ,0));
int top = edges.size() ;
G[from].push_back(top-2);
G[ to ].push_back(top-1);
}
inline void Init(int n,int s,int t){
this -> n = n ;
this -> s = s ;
this -> t = t ;
edges.clear();
for (int i=0;i<=n;i++)G[i].clear();
}

inline bool BFS(){
memset(vis,0,sizeof(vis));
queue<int>Q;
Q.push(s);d[s]=0;vis[s]=1;
while (!Q.empty()){
int x=Q.front();Q.pop();
for (int i=0;i<G[x].size();i++){
Edge &e=edges[G[x][i]];
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}
inline int DFS(const int& x,int a){
if (x==t||a==0){return a;}
int flow = 0, f;
for (int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow += f;
edges[G[x][i]^1].flow-=f;//ϲߍ
flow+=f; a-=f;
if (!a) break;
}
return flow;
}
inline int maxFlow(){return maxFlow(s,t);}
inline int maxFlow(int s, int t){
int flow = 0;
for (;BFS();){
memset(cur,0,sizeof(cur));
flow += DFS(s,INF) ;
}
return flow;
}
inline void buildEuler(int n){
for (int i=1;i<=n;i++){
for (int j=0;j<G[i].size();j++){
Edge &e = edges[G[i][j]];
if (e.to==s||e.to==t) continue ;
if (!e.cap)continue;
if (e.flow==e.cap)gg.AddEdge(e.to,e.from);
else gg.AddEdge(e.from, e.to);
}
}
}
} g ;

int d[N];//degree = out - in
bool work(int n){
int flow = 0;
for (int i=1;i<=n;i++){
if (d[1]&1)return 0;
if (d[i]>0){
g.AddEdge(g.s,i,d[i]>>1);
flow += d[i]>>1;
}else if (d[i]<0)
g.AddEdge(i,g.t,-(d[i]>>1));
}
if (flow != g.maxFlow()) return 0;
return 1;
}

int main(){
//freopen("in.txt","r",stdin);
int T,x,y,n,m;
scanf("%d",&T);
for (char ch;T--;){
scanf("%d%d",&n,&m);
g.Init(n,0,n+1);
gg.Init(n);
memset(d,0,sizeof(d));
for (int i=1;i<=m;i++){
scanf("%d%d %c\n",&x,&y,&ch);
if (ch=='D') gg.AddEdge(x,y);
else g.AddEdge(x,y,1);
d[x]++;d[y]--;//Degree
}
if (!work(n))puts("No euler circuit exist");
else {
g.buildEuler(n);
gg.getEulerCircle();
}
if (T)puts("");
}
return 0;
}

前行星的dinic板

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
struct Dinic
{
struct Edge{
int from,to,cap,flow,nxt;
Edge(){}
Edge(int u,int v,int c,int f,int n):
from(u),to(v),cap(c),flow(f),nxt(n){}
}edges[N];
int n, s, t, E, head[N];
bool vis[N]; //use when bfs
int d[N],cur[N];//dist,now edge,use in dfs
inline void AddEdge(int f,int t,int c){
edges[++E] = Edge(f,t,c,0,head[f]);
head[f] = E;
edges[++E] = Edge(t,f,0,0,head[t]);
head[t] = E;
}
inline void Init(int n,int s,int t){
this -> n = n ; E = -1;
this -> s = s ; head[s] = -1;
this -> t = t ; head[t] = -1;
for (int i=0;i<=n;i++) head[i] = -1;
}

inline bool BFS(){
memset(vis,0,sizeof(vis));
queue<int >Q;
d[s] = 0; vis[s] = 1;
for (Q.push(s);!Q.empty();){
int x = Q.front(); Q.pop();
for (int nxt,i = head[x];i!=-1;i = nxt){
Edge &e = edges[i]; nxt = e.nxt;
if (vis[e.to]||e.cap<=e.flow)continue;
vis[e.to]=1;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
return vis[t];
}
inline int DFS(const int& x,int a){
if (x==t||a==0){return a;}
int flow = 0, f, nxt;
for (int& i=cur[x];i!=-1;i=nxt){
Edge& e = edges[i]; nxt = e.nxt;
if (d[x]+1!=d[e.to])continue;
if ((f=DFS(e.to,min(a,e.cap-e.flow)))<=0)continue;
e.flow += f;
edges[i^1].flow-=f;//反向边
flow+=f; a-=f;
if (!a) break;
}
return flow;
}
inline int maxFlow(){return maxFlow(s,t);}
inline int maxFlow(int s, int t){
int flow = 0;
for (;BFS();){
for (int i=0;i<=n;i++)cur[i]=head[i];
flow += DFS(s,INF) ;
}
return flow;
}
inline void buildEuler(int n){
for (int i=1;i<=n;i++){
for (int nxt,j=head[i];j!=-1;j=nxt){
Edge &e = edges[j]; nxt = e.nxt;
if (e.to==s||e.to==t) continue ;
if (!e.cap)continue;
if (e.flow==e.cap)gg.AddEdge(e.to,e.from);
else gg.AddEdge(e.from, e.to);
}
}
}
} g ;