luogu2740 [USACO4.2]草地排水Drainage Ditches 最大流EK

练一下最大流

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int n, m, ron[205][205], pre[205], uu, vv, ww, vis[205];
queue<int> d;
int ek(){
	int maxFlow=0;
	while(1){
		memset(vis, 0, sizeof(vis));
		vis[1] = 0x3f3f3f3f;
		d.push(1);
		while(!d.empty()){
			int x=d.front();
			d.pop();
			for(int i=1; i<=n; i++)
				if(!vis[i] && ron[x][i]>0){
					vis[i] = min(vis[x], ron[x][i]);
					pre[i] = x;
					d.push(i);
				}
		}
		if(!vis[n])	break;
		maxFlow += vis[n];
		int hs=n;
		while(pre[hs]){
			ron[pre[hs]][hs] -= vis[n];
			ron[hs][pre[hs]] += vis[n];
			hs = pre[hs];
		}
	}
	return maxFlow;
}
int main(){
	cin>>m>>n;
	for(int i=1; i<=m; i++){
		scanf("%d %d %d", &uu, &vv, &ww);
		ron[uu][vv] += ww;
	}
	printf("%d
", ek());
	return 0;
}