POJ 1273 Drainage Ditches_涅槃phy的博客-程序员秘密

技术标签: 网络流  

Description

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

Input

The input includesseveral cases. For each case, the first line contains twospace-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 ofintersections points for those ditches. Intersection 1 is the pond. Intersectionpoint 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 intersectionsbetween which this ditch flows. Water will flow through this ditch from Si toEi. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water willflow through the ditch.

Output

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

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

50

题目大意:N条路,M个点。告诉N条路的起点、终点以及流量,求从1M点的最大流。

方法:这是去年暑假写的题了,也是写的第一道最大流的题。就是一个裸的最大流问题。就不多说了,就一个模板就完了

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/lphy2352286B/article/details/19282277

智能推荐

2022年,保研大数据方向推荐吗?_Baoyan_cs的博客-程序员秘密

写在前面网络的飞速发展(网络传输速度的提高、网络存储能力的提升)以及短视频时代的兴起,使得网络上传输/存储的数据量呈爆发式增长。而网络上数据量的增大,对传统的数据操作方式提出了新的挑战。为了解决这一挑战,大数据应运而生。作为一门新兴的专业,很多小伙伴对其了解程度不够。今天,岛主就为大家解析大数据专业的含金量,以及是否值得选择这一专业。一、当今时代大数据的重要性1. 政府大力支持近几年来,大数据的飞速发展为国家、社会、企业的发展做出了不小的贡献。党中央、国务院高度重视大数据在推动社会经

[Jmeter] Run Command to generate a specific listener’s chart report_weixin_30335575的博客-程序员秘密

Run Command to generate a specific listener’s chart report:Download cmdrunner-2.0.jar : https://jmeter-plugins.org/wiki/PluginsManagerAutomated/Find the plugin type in this URL:https://jmeter-...

linux内核内存管理 slab_alloc_node代码精读_Teddei的博客-程序员秘密

核心代码片段transaction id的重要作用准备工作 L2504-L2507barrier L2518内核per-cpu变量是没那么简单的一件事情,这和per-thread即thread local data完全是两个概念!!核心代码片段transaction id的重要作用 以及 L2521 注释 cmpxchg的每个CPU core上

Git 克隆文件报错:OpenSSL SSL_read: SSL_ERROR_SYSCALL, errno 10054; Failed to connect to github.com port 44_飞啊飞我的骄傲放纵-未来全栈工程师的博客-程序员秘密

造成这个错误的原因很有可能是网络不稳定,连接超时导致的如果再次尝试后依然报错,可以执行下面的命令 git config --global http.sslVerify false修改git设置,解除ssl验证,然后在尝试克隆,就成功了。...

python爬取重定向的网页_python爬虫解决网页重定向问题_weixin_39642998的博客-程序员秘密

function showImg(url) {var frameid = 'frameimg' + Math.random();window.img = 'window.onload = function() { parent.document.getElementById(\'' + frameid + '\').height = document.getElementById(\'img\')...

js new Date 创建时间默认是8点_烟草的香味.的博客-程序员秘密

起因最近在写一个页面,需要用到时间控制。然后我通过new Date()传入日期字符串创建了一个对象,并与当前时间做时间戳比较,结果12点刚过,就出问题了。举个栗子:// 假设当前时间是2019年12月22日0点20分new Date('2019-12-22').getTime() &lt; new Date().getTime()// 上面的结果是什么?正常来说应该是true吧...

随便推点

DOS命令_南京金鱼的博客-程序员秘密

2010-12-01DOS命令大全net use \\ip\ipc$ &quot; &quot; /user:&quot; &quot; 建立IPC空链接 net use \\ip\ipc$ &quot;密码&quot; /user:&quot;用户名&quot; 建立IPC非空链接 net use h: \\ip\c$ &quot;密码&quot; /user:&quot;用户名&quot; 直接登陆后映射对方C:到本地为H: net use h: \\ip\c$ 登陆后映射对方C

f,s,z_ffittiff的博客-程序员秘密

傅里叶变换在物理学、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用(例如在信号处理中,傅里叶变换的典型用途是将信号分解成幅值分量和频率分量)。 傅里叶变换能将满足一定条件的某个函数表示成三角函数(正弦和/或余弦函数)或者它们的积分的线性组合。在不同的研究领域,傅里叶变换具有多种不同的变体形式,如连续傅里叶变换和离散傅里叶变换。 傅里叶变换是一种

CSS预处理语言Less常用语法_刻刻帝丶的博客-程序员秘密

Less是一种动态样式语言,属于css预处理语言的一种 它使用类似CSS的语法为CSS的赋予了动态的特性 如变量,继承,运算,函数等,更方便css的编写和维护实现css模块化less 可以在多种语言,环境中使用,包括浏览器端、桌面客户端、服务端 其实它非常简单 要想使用less我们需要下载它 我选择利用npm包管理器下载 npm install less less-loader修改配置文

【Swagger3】SpringBoot项目集成Swagger3_lixin123cn的博客-程序员秘密

资料:swagger 官网:swagger.iospringfox 官网:springfoxspringfox Github 仓库:springfox / springfoxspringfox-demos Github 仓库:springfox / springfox-demosspringfox Maven 仓库:Home » io.springfoxSpringFox 3.0.0 发布:官方说明:SpringFox 3.0.0 发布了,SpringFox 的前身是 swagger-

js获取html中svg标签,点击svg获取元素 怎么在svg元素上显示文字_砺石商业评论的博客-程序员秘密

d3.js怎么选中svg当前元素怎么对svg里面元素怎么添加点击事件同样遇到的问题,而且svg下放image的话再放其他标签就被image盖住了如何获取并操作html中用标签嵌入的svg元素SVG 文件可通过以下标签嵌入 HTML 文档:、 或者 。 推荐使用标签, 标签被所有主流的浏览器支持,并允许使用脚本。如何用JS实现鼠标划过SVG中的元素 弹出DIV层onmousemove 必须写在svg...

消息队列 64式 : 2、oslo.messaging消息处理源码分析_天地一扁舟的博客-程序员秘密

目标:弄清楚oslo messaging中executor为threading的处理过程1 总入口ceilometer/collector.pyclass CollectorService(cotyledon.Service): """Listener for the collector service.""" def __init__(self, worker_id)...

推荐文章

热门文章

相关标签