站点图标 陌路寒暄

4.2.1 Drainage Ditches 草地排水

code

4.2.1 Drainage Ditches 草地排水

时间： 1ms        内存：64M

描述：

在农夫约翰的农场上，每逢下雨，贝茜最喜欢的三叶草地就积聚了一潭水。这意味着草地被水淹没了，并且小草要继续生长还要花相当长一段时间。因此，农夫约翰修建了一套排水系统来使贝茜的草地免除被大水淹没的烦恼（不用担心，雨水会流向附近的一条小溪）。作为一名一流的技师，农夫约翰已经在每条排水沟的一端安上了控制器，这样他可以控制流入排水沟的水流量。

农夫约翰知道每一条排水沟每分钟可以流过的水量，和排水系统的准确布局（起点为水潭而终点为小溪的一张网）。需要注意的是，有些时候从一处到另一处不只有一条排水沟。

根据这些信息，计算从水潭排水到小溪的最大流量。对于给出的每条排水沟，雨水只能沿着一个方向流动，注意可能会出现雨水环形流动的情形。

输入：

第1行: 两个用空格分开的整数N (0 <= N <= 200) 和 M (2 <= M <= 200)。N是农夫约翰已经挖好的排水沟的数量，M是排水沟交叉点的数量。交点1是水潭，交点M是小溪。 第二行到第N+1行: 每行有三个整数，Si, Ei, 和 Ci。Si 和 Ei (1 <= Si, Ei <= M) 指明排水沟两端的交点，雨水从Si 流向Ei。Ci (0 <= Ci <= 10,000,000)是这条排水沟的最大容量。

输出：

输出一个整数，即排水的最大流量。

示例输入：

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

示例输出：

50

提示：

参考答案（内存最优[1612]）：

#include <iostream>
using namespace std;

#define MAXN 210
#define inf 2100000000

int n,m;
int mat[MAXN][MAXN];
int source,sink;
int flow[MAXN][MAXN];

int max_flow()
{
	int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
	if(source == sink) 
		return inf;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; flow[i][j++] = 0);
	for (; ;)
	{
		for(i = 1; i <= n; pre[i++] = 0);
		pre[t = source] = source+1, d[t] = inf;
		for(p = q = 0; p <= q && !pre[sink]; t = que[p++])
			for(i = 1; i <= n; i++)
				if(!pre[i] && (j = mat[t][i]-flow[t][i]))
					pre[que[q++] = i] = t+1, d[i] = d[t] < j?d[t]:j;
				else if(!pre[i] && (j = flow[i][t]))
					pre[que[q++] = i] = -t-1, d[i] = d[t]<j?d[t]:j;
		if(!pre[sink]) 
			break;
		for(i = sink; i != source;)
			if(pre[i] > 0)
				flow[pre[i]-1][i] += d[sink], i = pre[i]-1;
			else
				flow[i][-pre[i]-1] -= d[sink],i = -pre[i]-1;
	}
	for(j = 0, i = 1;i <= n; j += flow[source][i++]);
	return j;
}


int main()
{
	int i;
	int s,e,c;
	cin >> m >> n;
	source = 1;
	sink = n;
	for(i = 1; i <= m; i++)
	{
		cin >> s >> e >> c;
		mat[s][e] += c;
	}
	cout << max_flow() << endl;
	return 0;
}

参考答案（时间最优[12]）：

#include <iostream>
using namespace std;

#define MAXN 210
#define inf 2100000000

int n,m;
int mat[MAXN][MAXN];
int source,sink;
int flow[MAXN][MAXN];

int max_flow()
{
	int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
	if(source == sink) 
		return inf;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; flow[i][j++] = 0);
	for (; ;)
	{
		for(i = 1; i <= n; pre[i++] = 0);
		pre[t = source] = source+1, d[t] = inf;
		for(p = q = 0; p <= q && !pre[sink]; t = que[p++])
			for(i = 1; i <= n; i++)
				if(!pre[i] && (j = mat[t][i]-flow[t][i]))
					pre[que[q++] = i] = t+1, d[i] = d[t] < j?d[t]:j;
				else if(!pre[i] && (j = flow[i][t]))
					pre[que[q++] = i] = -t-1, d[i] = d[t]<j?d[t]:j;
		if(!pre[sink]) 
			break;
		for(i = sink; i != source;)
			if(pre[i] > 0)
				flow[pre[i]-1][i] += d[sink], i = pre[i]-1;
			else
				flow[i][-pre[i]-1] -= d[sink],i = -pre[i]-1;
	}
	for(j = 0, i = 1;i <= n; j += flow[source][i++]);
	return j;
}


int main()
{
	int i;
	int s,e,c;
	cin >> m >> n;
	source = 1;
	sink = n;
	for(i = 1; i <= m; i++)
	{
		cin >> s >> e >> c;
		mat[s][e] += c;
	}
	cout << max_flow() << endl;
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。

退出移动版