Dinic求最大流
#include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = 200010, inf = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], c[M], ne[M], idx;
int q[N], dep[N], cur[N];
void add(int u, int v, int w)
{
e[idx] = v, c[idx] = w, ne[idx] = h[u], h[u] = idx ++ ;
e[idx] = u, c[idx] = 0, ne[idx] = h[v], h[v] = idx ++ ;
}
bool bfs()
{
memset(dep, -1, sizeof dep);
int hh = 0, tt = 0;
q[0] = S, dep[S] = 0;
cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dep[j] == -1 && c[i])
{
dep[j] = dep[t] + 1;
cur[j] = h[j];
if (j == T)return true;
q[++ tt] = j;
}
}
}
return false;
}
int find(int u, int limit)
{
if (u == T)return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int j = e[i];
if (dep[j] == dep[u] + 1 && c[i])
{
int t = find(j, min(c[i], limit - flow));
if (!t)dep[j] = -1;
c[i] -= t, c[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic()
{
int res = 0, flow;
while (bfs())while (flow = find(S, inf))res += flow;
return res;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &S, &T);
memset(h, -1, sizeof h);
while (m -- )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
printf("%d\n", dinic());
return 0;
}