[板子] 网络最大流

题目链接

Code

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
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <queue>
const int N = 10010,M = 200010,inf = 0x3f3f3f3f;
inline int getint()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
struct Dinic
{
int head[N],next[M],to[M],cap[M],flow[M],tot,d[N],cur[N],s,t;std::queue<int> Q;
#define _(a) memset(a,-1,sizeof(a))
Dinic(int s,int t){this->s = s;this->t = t;init();}inline void init(){tot = -1;_(head);}
inline void addedge(int u,int v,int w){next[++tot] = head[u];to[tot] = v;cap[tot] = w;head[u] = tot;}
inline void adde(int u,int v,int w){addedge(u,v,w);addedge(v,u,0);}
inline int bfs()
{
_(d);d[s] = 0;Q.push(s);
while(!Q.empty())
{
int u = Q.front();Q.pop();
for(register int i = head[u],v = to[i];~i;v = to[i = next[i]]) if(cap[i] > flow[i] && !~d[v]) {d[v] = d[u] + 1;Q.push(v);}
}
return ~d[t] ? 1 : 0;
}
inline int dfs(int u,int mf)
{
if(u == t)return mf;
int ret = 0;for(register int i = ~cur[u] ? cur[u] : head[u],v = to[i],a;i >= 0;v = to[i = next[i]]) if(cap[i] > flow[i] && d[v] == d[u] + 1 && (a = dfs(v,std::min(cap[i] - flow[i],mf - ret))))
{
ret += a;flow[i] += a;flow[i ^ 1] -= a;cur[u] = i;
if(mf == ret)return ret;
}
cur[u] = -2;return ret;
}
inline int dinic(){int ret = 0;while(bfs()){_(cur);ret += dfs(s,inf);}return ret;}
};
int main()
{
int n = getint(),m = getint(),s = getint(),t = getint();Dinic D(s,t);
for(int i = 1,u,v,w;i <= m;i++) {u = getint();v = getint();w = getint();D.adde(u,v,w);}
printf("%d\n",D.dinic());
return 0;
}