-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dinic.cpp
129 lines (126 loc) · 3 KB
/
Dinic.cpp
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
// Dinic Maximum Flow algorithm O(E V^2)
template<typename T>
class MaximumFlow{
private:
struct edge{int to; T cap; int rev;};
vector<vector<edge> > Graph;
vector<int> level, iter; //sからの距離,どこまで調べたか
void bfs(int s){
fill(begin(level), end(level), -1);
queue<int> q;
level[s]=0;
q.push(s);
while(!q.empty()){
int v=q.front(); q.pop();
for(auto e : Graph[v]){
if(e.cap>0 && level[e.to]<0){
level[e.to] = level[v]+1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T f){
if(v==t) return f;
for(int &i=iter[v]; i<(int)Graph[v].size(); i++){
auto &e = Graph[v][i];
if(e.cap>0 && level[v]<level[e.to]){
T d = dfs(e.to, t, min(f, e.cap));
if(d>0){
e.cap -= d;
Graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
MaximumFlow(int n){
Graph = vector<vector<edge> >(n, vector<edge>());
level = vector<int>(n);
iter = vector<int>(n);
}
T max_flow(int s, int t){
T flow=0;
while(true){
bfs(s);
if(level[t] < 0) break;
fill(begin(iter), end(iter), 0);
T f;
while((f=dfs(s,t,INF)) > 0){
flow += f;
}
}
return flow;
}
void add_edge(int from, int to, T cap){
int tos = Graph[to].size(), froms = Graph[from].size();
Graph[from].push_back(((edge){to, cap, tos}));
Graph[to].push_back(((edge){from, 0, froms}));
}
}; // END class MaximumFlow
// for POJ
// Dinic Maximum Flow algorithm O(E V^2)
template<typename T>
class MaximumFlow{
private:
struct edge{int to; T cap; int rev;};
vector<vector<edge> > Graph;
vector<int> level, iter; //sからの距離,どこまで調べたか
void bfs(int s){
fill(all(level), -1);
queue<int> q;
level[s]=0;
q.push(s);
while(!q.empty()){
int v=q.front(); q.pop();
rep(i, Graph[v].size()){
edge e = Graph[v][i];
if(e.cap>0 && level[e.to]<0){
level[e.to] = level[v]+1;
q.push(e.to);
}
}
}
}
T dfs(int v, int t, T f){
if(v==t) return f;
for(int &i=iter[v]; i<(int)Graph[v].size(); i++){
edge &e = Graph[v][i];
if(e.cap>0 && level[v]<level[e.to]){
T d = dfs(e.to, t, min(f, e.cap));
if(d>0){
e.cap -= d;
Graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
public:
MaximumFlow(int n){
Graph = vector<vector<edge> >(n, vector<edge>());
level = vector<int>(n);
iter = vector<int>(n);
}
T max_flow(int s, int t){
T flow=0;
while(true){
bfs(s);
if(level[t] < 0) break;
fill(all(iter), 0);
T f;
while( (f=dfs(s,t,INF)) > 0){
flow += f;
}
}
return flow;
}
void add_edge(int from, int to, T cap){
int tos = Graph[to].size(), froms = Graph[from].size();
Graph[from].pb(((edge){to, cap, tos}));
Graph[to].pb(((edge){from, 0, froms}));
}
}; // END class MaximumFlow