4 2 3 2 11. . 2 3 0 10, 4 3 0 19. . Answer: Impossible Source: AC program 4 2 0 0 47, 3 17 17 25, 4 0 0 38. 1 17 17 31, 3 0 0 23, 4 0 0 96. 1 0 0 96, 2 0 0 48, 4 17 17 91. . = 69 2 0, 3 17, 4 1. 1 18, 3 0, 4 0. 1 0, 2 0, 4 17. . 8 . 1 0 0 39, 5 13 13 21. 5 0 0 87, 8 41 41 92. 5 38 38 85. 6 41 41 14, 8 10 10 49. 2 10 10 69, 3 41 41 58, 4 0 0 73. 6 3 3 59. . = 49 . 1 0, 5 13. 5 0, 8 41. 5 38. 6 40, 8 11. 2 10, 3 41, 4 0. 6 3. . Edited by author 16.06.2008 04:40 Why not 4 2 0 0 47, 3 17 17 25, 4 0 0 38. 1 17 17 31, 3 0 0 23, 4 0 0 96. 1 0 0 96, 2 0 0 48, 4 17 17 91. . = 61 2 0, 3 16, 4 1. 1 17, 3 1, 4 0. 1 0, 2 0, 4 17. . For those confused by this test case. I believe svr's answer is right as my AC program outputs this very result. Slobodan has AC as well though. Yes. We can decrease flow on some pipeline( if the flow on some pipeline is greater zero ). And this operation is free!!! =) Why? What is fucking test 31?? Does anybody know? I use Dijkstra on residue network from several sources to sink. For every edge (u, v): 1) if flow < capacity then cost = 0 2) if flow > 0 then graph contains back edge (v, u) with cost = 0. Dijkstra initialize sources (nodes of the graph, where excess of flow > 0) with cost = 0. We find shortest path from one of sources to the sink. Then we make changes with edges used in shortest path and out results. What's wrong?? Please someone explain sample test case. I don't understand how we can push flow 2 through 1->2 (output shows that) if in the input there is flow capacity 1? In the second line of the input there is 2 1 1 1, 3 1 1 3. that means there is pipeline between 1 and 2 with max flow 1, but there is already 1 flow, so we can't push anything more or something else...? Thank you in advance. read carefully what "d" means. First i had WA 20, because of wrong apporach, now WA 26... Maybe somebody have some test ar now something similar to this testcase. Btw, I am using dijkstra from source to sink with backegde cost of zero. Or this is also wrong? I was getting WA26 when use this declaration for "INFINITE" constant: const __int64 INF = (__int64)1e17; ... when I change it for next one: const __int64 INF = 10000....... ; I get AC! In test#6 from station N oil is transported to other station. Edited by author 18.09.2007 00:48 Test #6 is correct, read the problem statement more carefully. What is the output for the following test? 4 2 3 3 1. 3 3 3 1, 4 1 0 1. 4 4 4 1. . Is minimum sufficient amount of money 0 or 1 ??? How can it be equal to 0? I think correct answer is: 1 2 3. 4 0, 3 3. 4 5. . Well, the problem statement is not clear. Obviously, nodes 1 and 3 can produce oil, so technically we can reorganize whole network as follows: 1. Substract one item of flow from 2 to 3, since 3 can produce oil itself and easily can increase it's output by 1 2. Add flow of value 1 from node 2 to 4 Thus, to increase flow by one we need not to increase any capacities and answer is 0. Edited by author 12.01.2007 13:05 Hm, I think, you can be right... I'll try to implement it... Yes, the idea described above is really right... But this idea means that we must find min cost flow with value 1 unit greater from 0-flow initial flow not as additional flow,or make absolute new flow distribution. It seems that there is additional difficulty that cost per- unit is 0 before capacity and c[i] after capacity, or discontinious. Thus problem seems non-standard.Don't say us secret, best celebration to find ourselves. Why Deikstra from N-th node to sources backwards get WA20? Transfer of one indivisible unit of the flow obiously is Deikstra best. What trick may be in test 20? May be excess of the bound 10000 is forbidden for any money? AC after year! Djkstra of course, but in residue net. Action of "zaem" just is equal to going along residue net. Beside this the problem actually is not linear, just piecewise linear. There is classical method of adding additional edge in this situation. During a long time I could not understand why we may diminish flow along edges but sourses production no. This becaurse in statement there are not words about such diminishing but about increasing there are but only in limits from 0 to 1. Edited by author 30.11.2008 22:06 Dijkstra - you should spell surnames properly Edited by author 06.01.2007 14:03 I've checked all the numbers in the input - they are correct. But Dijkstra still gets WA #20... May be, problem in some tricky cases like N = 1? I output "Impossible" in such a case... In the former statement of the problem number of quadruples was not exceed 1000000. Now - not more than 100000. VERY bad fact - I think many people (including me) don't solve this problem due to it... When problemsetters will stop such an idiotism? I always get stuck at test nr.4 due to an exceeded memory limit. Can't figure out why, tried to tune all structures and algorithm for low consumption. Is it possible to get a test input file to check this ? Regards, Christian Is it guaranteed that there is station, where incoming flow is less than outgoing flow? Could I output pairs in any order, or they should be sorted by vertex? First submit: WA #6, I print information about all pipes. Second submit: AC,I thought, that, if flow at pipe=0, then we don't print information about it at output. Rejudge - WA #2 at Second Submit. Third submit: AC, I print information about all pipes. I don't understand why my first submit is not AC after rejudge. Is it true, that ALL submits rejudged?
Edited by author 06.11.2006 23:20 Edited by author 06.11.2006 23:20 Your submission 1378260 has WA#6 because it didn't output all edges. I can send you this submission and simple fail-test. Thanks! I thought, that only last submit was rejudged. And where does the oil come from? Station 1? |
|