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\n", ek());

	return 0;

}

巴特西

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

最新文章

热门文章