本文主要是介绍hunnu 11545小明的烦恼——找路径 (最大流),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
小明的烦恼——找路径 |
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB |
Total submit users: 45, Accepted users: 37 |
Problem 11545 : No special judgement |
Problem description |
小明真的是个很厉害的人,每当老师有什么事时,总是会找到小明,二小明也总能解决,所以老师决定给小明一个奖励,给他额外的假期。小明当然很高兴,因为小明终于可以如愿的出去旅游了。小明旅游的第一站到了美丽的长沙,到了长沙当然免不了要去参观古色古香的的湖南师范大学了,小明在师大校园里愉快的玩耍,不时瞅一眼从他身边经过的美女,也感叹这个校园古老建筑带给他的震撼。临近中午了,小明走到了理学院大门前,瞬间就被吸引了,于是就走了进去,在理学院的一个教室外面,小明看到有个带眼睛的男生在皱眉头,好像是被什么难题卡住了,小明的慈悲之心油然而生,于是就走了进去。于是题目就来了: 有N个城市,有些城市有道路相连,但这些道路中间并没有加油站(每个城市里面有加油站可以补给),现在有个工程师要找到T条不同的路径从1号城市到N号城市,两条路径是不同的当且仅当不经过相同的边,现在告诉你工程师的汽车的最大载油量C和经过每条道路所要消耗的油量,问你这个工程师能不能完成任务。 |
Input |
由多组case: 每组case第一行有4个整数N,M,T,C,N<=200;C<=1000000; 然后有M行。每一行有3个整数,a,b,c,代表从a城市到b城市需要c的油量。c<=1000000;如果两个城市之间有多条边,则视为不同的边。 |
Output |
对于每个case: 如果工程师能够完成任务,输出YES,不然输出NO。 |
Sample Input |
7 9 2 5 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 7 9 2 4 1 2 2 2 3 5 3 7 5 1 4 1 4 3 1 4 5 7 5 7 1 1 6 3 6 7 3 |
Sample Output |
YES NO 解题:假设每条可行边的流限最大为1,则根据网络流的性质:每个点的 流进量==流出量,守恒。所以一条边只能属于一条路。
|
这篇关于hunnu 11545小明的烦恼——找路径 (最大流)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!