EK 求最大流
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, M = 20005,INF=1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], pre[N];
bool st[N];
void add(int a,int b,int c){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
bool bfs(){
int hh = 0, tt = 0;
memset(st, 0, sizeof(st));
q[0] = S, st[S] = 1,d[S] = INF;
while(hh<=tt){
int t = q[hh++];
for (int i = h[t]; ~i;i=ne[i]){
int ver = e[i];
if(!st[ver]&&f[i]){
st[ver] = 1;
d[ver] = min(d[t], f[i]);
pre[ver] = i;
if(ver==T) return 1;
q[++tt] = ver;
}
}
}
return 0;
}
int EK(){
int r = 0;
while(bfs()){
r += d[T];
for (int i = T; i != S;i=e[pre[i]^1])
f[pre[i]] -= d[T], f[pre[i]^1] += d[T];
}
return r;
}
int main(){
memset(h, -1, sizeof(h));
cin >> n >> m >> S >> T;
while(m--){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << EK() << endl;
return 0;
}