Gargoyle
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 139 Accepted Submission(s): 22
Problem Description
Gargoyles can trace their history back many thousands of years to ancient Egypt, Greece, and Rome. Terra cotta waterspouts were formed in the shapes of animals such as lions and birds to serve the physical function of running the
rainwater away from the walls and foundations of buildings, and the spiritual function of protecting from evil forces.
Have you ever dreamed of creating your own castle with a lot of beautiful gargoyles on the walls? To your knowledge,
the speed of water coming out of each gargoyle should be identical, so an elaborately designed water system is required.
The water system consists of a huge reservoir and several interconnecting water pipes. Pipes cannot save water, so the total incoming and outgoing speed of water should be equal at each connection.
All the water from gargoyles flows into the reservoir, which is located at the bottom of the castle. Some pipes are connecting the reservoir, but water can only go from the reservoir to pipes, but never from pipes back to the reservoir. A micro-processor is installed inside each pipe, so the speed of water could easily be controlled. However, the microprocessors consume electricity. The exact cost in each pipe is proportional to the speed of water. If the cost constant in the i-th pipe is ci, the electricity cost in that pipe is civi, where vi is the speed of water in that pipe. Write a program to find the optimal configuration of the water system (i.e. the water speed in each pipe) of your dream castle, so that the total cost is minimized. It is always possible to build a water system.
Input
The input consists of several test cases. The first line of each case contains three integers n, m and k (1 ≤ n ≤ 25, 1 ≤ m ≤ 50, 1 ≤ k ≤ 1000), the number of gargoyles, the number of pipe connections and the number of pipes. The following k lines each contains five integers a, b, l, u, c (0 ≤ a, b ≤ n + m, 0 ≤ l ≤ u ≤ 100, 1 ≤ c ≤ 100), describing each pipe. a and b
are the incoming and outgoing vertex number (reservoir is 0, gargoyles are numbered 1 to n, pipe connections are numbered n + 1 to n + m), lower-bound and upper-bound of water speed, and the cost constant. No pipe connects two identical vertices. For every pipe, the incoming vertex will never be a gargoyle, and the outgoing vertex will never be the reservoir. For every pair of vertices, there could be at most one pipe connecting them (if a pipe is going from a to b, no pipes can go from a to b, or from b to a). The last test case is followed by a single zero, which should not be processed.
Output
For each test case, print the case number and minimal cost to two decimal places.
Sample Input
3 1 4
0 4 8 15 5
4 1 2 5 2
4 2 1 6 1
4 3 3 7 2
0
Sample Output
Source
Recommend
lcy
06年亚洲区域赛西安赛区的一道网络流，相当犀利......我WA很久很久才勉强过了.......
一．总体分析
本题给出了一个网络流的模型。以积水池为源点，每个连接点和喷水口为结点，另外建立一个超级汇，每个喷水口向超级汇连一条边。题目就是求一个有上下界的最小费用流，其中到汇点的每一条边的流量必须相等(*)。
很多文献对有上下界的费用流进行了讨论，本文不再赘述。本文主要讨论解决如何解决(*)的要求。
二．判断可行流
我们不妨设所有连接到汇点的边的流量均为F，我们要做的第一步就是：判断是否存在这样一组可行流使得F = F0成立。
我们不妨给每一条连接到汇点的边建立上下界[0，F0]。我们给出以下引理：
引理一：存在满足使得F0的可行流，当且仅当该网络的最大流为F0N。
引理二：若最大流小于F0N，则不存在F >= F0的可行流；
引理三：若不存在可行流，则不存在F <= F0的可行流；
由引理二、三可知：
引理四：
存在可行流的F的定义域为一段连续的区间[low, top]。
根据引理二、三和四，我们不难使用二分法找出这一段F的可行区间[low, top]。
三．找出最小费用流
记cost(F)表示在F成立的最小费用。我们猜测，cost(F)与F成正比！
感觉上，F越大，流量越大，那么每条边上消耗的费用也就越大，所以猜想应该成立。可惜的是，按照该想法提交是无法通过测试数据的。因为：
大家不免疑问，单调函数不也是凸的么？
注意到有上下界的最小费用由两部分构成：附加网络的最小费用及残余网络的最小费用。注意到前者是关于F不增的后者是关于F不减的，如果前者的递减速度大于后者的递增速度，那么cost(F)将成为下凸函数。
四．算法流程
由于最小费用流的时间复杂度不好分析，本文直接认为是O(kN2)，其中k表示增广次数，算法总的时间复杂度为O(kN2logC)。