EK求最大流
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 20010, inf = 0x3f3f3f3f;
int n, m, s, t;
int h[N], e[M], c[M], ne[M], idx;
int q[N], d[N], pre[M];
bool st[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(st, 0, sizeof st);
int hh = 0, tt = 0;
q[0] = s, st[s] = true, d[s] = inf;
while (hh <= tt)
{
int u = q[hh ++ ];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j] && c[i])
{
st[j] = true;
pre[j] = i;
d[j] = min(d[u], c[i]);
if (j == t)return true;
q[++tt] = j;
}
}
}
return false;
}
int EK()
{
int res = 0;
while (bfs())
{
res += d[t];
for (int i = t; i != s; i = e[pre[i] ^ 1])
c[pre[i]] -= d[t], c[pre[i] ^ 1] += d[t];//在残余网络上修改
}
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", EK());
return 0;
}