HDU 2006 求奇数的乘积(水题)
877
2022-08-23
ACdream 1017 Fast Transportation (网络流+分层图)
Fast Transportation
Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
Submit Statistic Next Problem
Problem Description
I’m working for a huge transportation company, and this month we get a job that deliver Kimportant medicinal machines from city S to city T. Since the machines is so large that for each machine we should use a whole truck to carry it.
We live in a country contains N cities and M bidirectional roads, each road cost one day to passed. And your boss wants you, the best programmer, to find a plan which can deliver all machines in fewest days.
However with the unknown reasons, we can just use each road only once a day.
Sometimes a truck can choose not to go but wait at a city.
A city can hold any truck each day.
Input
There are multiple test cases.
In each test case, the first line contains five integers N, M, K, S and T. Next M lines each line contains two integers a, b, indicating a road connected the city a and city b. There is at most one road in any two cities, and no road connected one city to itself.
2 ≤ N ≤ 10, 1 ≤ M ≤ 20
1 ≤ K ≤ 50, 1 ≤ S, T ≤ N, S != T
Output
For each test, please output an integer indicating the fewest days to deliver all machine to the destination.
Sample Input
6 7 4 1 61 22 33 55 61 44 64 3
Sample Output
4
Hint
The road can be traveled in both directions, but remember that each day only one truck can travel through it, in particular, two trucks cannot simultaneously travel the same road in opposite directions
Source
dut200901102
Manager
nanae
题意:给定一个无向图,求要用最少的时间从源点S向终点T运送K件货物。要求: (1)从一个节点走到相邻节点用时1天; (2)一天中一条路只能使用一次。
题解:对于最后要求的最短时间,由于单调性,可以使用二分答案的策略。对于每次枚举的天数S,将图中的每个点都拆成S个,则全图变成S层(分层图)。规定同层之间不允许连边,对于原始图中的边(i,j),则在相邻两层中将对应的点从低的一层连上高的一层。设置超级源点,向第一层中的出发点连上一条容量为K的边,将每层中的目的地点向超级汇点连上一条容量无穷的边,然后求最大流是否等于K。我用了SAP。可以Dinic.....或者ISAP......
AC代码:
#include
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~