文档章节

poj 1273 Drainage Ditches

locusxt
 locusxt
发布于 2014/04/22 23:55
字数 625
阅读 296
收藏 1
第一道网络流, edmonds_karp
一开始,自己写了一个,能找到的所有数据都过了,可就是一直WA。
然后,就找了个模板。

Drainage Ditches
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 53435 Accepted: 20363

Description

Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch. 
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network. 
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle. 

Input

The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output

For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

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

Sample Output

50

Source


/*
 * @author cnjs.zhuting@gmail.com
 * 
 */
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
#define maxn 210
#define inf 1000000000
using namespace std;

int n = 0, m = 0;
int cap[maxn][maxn] = {0};

int edmonds_karp(int src, int dest)
{
	int flow_sum = 0;
	int cur_flow[maxn] = {0};
	int prev[maxn] = {0};
	queue<int> q;

	while(true)
	{
		memset(cur_flow, 0, sizeof(cur_flow));

		cur_flow[src] = inf;
		q.push(src);
		while(!q.empty())
		{
			int cur = q.front();
			q.pop();
			for (int i = 1; i <= n; ++i)
			{
				if (!cur_flow[i] && cap[cur][i] > 0)
				{
					q.push(i);
					if (cur_flow[cur] > cap[cur][i])
						cur_flow[i] = cap[cur][i];
					else
						cur_flow[i] = cur_flow[cur];
					prev[i] = cur;
				}
			}
		}

		if (cur_flow[dest] == 0)
			break;
		for (int i = dest; i != src; i = prev[i])
		{
			cap[prev[i]][i] -= cur_flow[dest];
			cap[i][prev[i]] += cur_flow[dest];
		}
		flow_sum += cur_flow[dest];

	}
	return flow_sum;
}

int main()
{
	int s = 0, d = 0, c = 0;
	while(scanf("%d%d", &m, &n) != EOF)
	{
		memset(cap, 0, sizeof(cap));

		for (int i = 0; i < m; ++i)
		{
			scanf("%d%d%d", &s, &d, &c);
			cap[s][d] += c;
		}
		printf("%d\n", edmonds_karp(1, n));
	}
	return 0;
}




© 著作权归作者所有

locusxt
粉丝 27
博文 140
码字总数 90989
作品 0
海淀
程序员
私信 提问
加载中

评论(1)

华_琼
华_琼
现在还在做Python开发么?还在北京否?很高兴认识你,如果还在做技术的话,有机会可以加QQ交流哦:1524583347
HDOJ 1532 Drainage Ditches (Ford-Fulkerson + EK + Dinic)

Drainage Ditches Time Limit: 2000/1000 MS(Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16953 Accepted Submission(s): 8019 Problem Description Ever......

my_sunshine26
2017/04/12
0
0
算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰
2016/04/02
160
1
一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404
2015/06/24
0
0
使用 BackBone 获取参数的一个问题

根据 Backbone 文档的做法,代码如下: 得到的参数是: http://localhost:8080/Items?[object%20Object] 而不是:http://localhost:1273/Items?page=1 我该如何传参数呢?...

华宰
2011/07/12
2.2K
1
POJ3723 《挑战程序设计竞赛》踩坑

我看书上的代码,觉得这一行有错误, 所以我就没这样写,我写的是 在codeblocks运行的好好的,来了poj一直报错,debug两个多小时,终于发现,书里的题目和poj上的题目,x,y表示的正好相反啊...

小太阳花儿
2017/12/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js如何控制table中的某一行动态置顶

两行代码搞定: $('#'+item.roadCode).fadeOut().fadeIn();//获取到需要置顶的行 $(".table").prepend($('#'+item.roadCode)); 其中,fadeOut()方法 作用 --- 从可见到隐藏 如下: prepend(......

码妞
今天
4
0
四种解决Nginx出现403 forbidden 报错的方法

我是在在本地用虚拟机中通过yum安装nginx的,安装一切正常,但是访问时报403, 于是查看nginx日志,路径为/var/log/nginx/error.log。打开日志发现报错Permission denied,详细报错如下: 1....

dragon_tech
今天
3
0
获取RestResultResponse返回的值

Springboot项目,需要调其他服务的接口,返回值类型是RestResultResponse 打断点的结果集是这个 打印出来的getData(): [{id=3336b624-8474-4dd9-bd5b-c7358687c877, paraNo=104, para=Postpo...

栾小糖
今天
4
0
【小学】 生成10以内的加减法

#!/usr/bin/env python# coding: utf-8from random import randrange# 题目的最大数值R_MAX = 10# 生成的题目的数量R_PAGE = 70# 生成减法列表def get_sub_list():...

Tensor丨思悟
今天
11
0
JavaScript设计模式——适配器模式

  适配器模式是设计模式行为型模式中的一种模式;   定义:   适配器用来解决两个已有接口之间不匹配的问题,它并不需要考虑接口是如何实现,也不用考虑将来该如何修改;适配器不需要修...

有梦想的咸鱼前端
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部