• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 7,comments - 3,trackbacks - 0

            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
            Case 1: 60.00
             

            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)。
            posted on 2011-10-15 22:16 LLawliet 閱讀(263) 評論(0)  編輯 收藏 引用 所屬分類: 網絡流
            久久综合九色综合久99| 性做久久久久久免费观看| 精品人妻伦一二三区久久 | 无码人妻少妇久久中文字幕蜜桃 | 久久久久久久女国产乱让韩| 色综合久久中文字幕无码| 久久99精品综合国产首页| 欧美久久综合九色综合| .精品久久久麻豆国产精品| 久久久久99精品成人片三人毛片 | 久久AV无码精品人妻糸列| 国内精品久久国产大陆| 久久无码国产专区精品| 久久夜色tv网站| 日韩久久久久久中文人妻| 久久午夜综合久久| 久久99精品国产麻豆宅宅| 久久99久国产麻精品66| 婷婷久久综合| 国产三级观看久久| 国产成人综合久久精品尤物| 久久精品99久久香蕉国产色戒 | 久久久噜噜噜久久熟女AA片 | 久久天天日天天操综合伊人av| 久久精品人人槡人妻人人玩AV| 亚洲国产成人精品久久久国产成人一区二区三区综| 国产精品久久久久久久久软件| 久久久久九国产精品| 韩国三级中文字幕hd久久精品| 好属妞这里只有精品久久| 91久久婷婷国产综合精品青草| 久久精品视频一| 中文字幕热久久久久久久| 久久综合伊人77777麻豆| 久久国产影院| 精品久久久久久久久久中文字幕| 精品一区二区久久久久久久网站| a级成人毛片久久| 久久精品国产99国产电影网 | 欧美激情精品久久久久| 91亚洲国产成人久久精品网址|