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)。