| ENG RUS | Timus Online Judge |
Обсуждение задачи 1505. Перекачка нефтиএসো নবীন দলে দলে, ছাত্রলীগের পতাকাতলে। Test Case [1] // Задача 1505. Перекачка нефти 16 сен 2016 13:44 4 2 3 2 11. . 2 3 0 10, 4 3 0 19. . 50541 Re: Test Case // Задача 1505. Перекачка нефти 31 май 2018 14:51 Answer: Impossible Source: AC program Slobodan tests [2] // Задача 1505. Перекачка нефти 16 июн 2008 04:40 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 svr Re: tests [1] // Задача 1505. Перекачка нефти 26 ноя 2008 09:59 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. . 50541 Re: tests // Задача 1505. Перекачка нефти 31 май 2018 14:50 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. Ilya Rasenstein (Lyceum #40) Can I decrease flow on some pipeline? (-) [1] // Задача 1505. Перекачка нефти 6 янв 2007 14:14 IgorKoval [PskovSU] Re: Can I decrease flow on some pipeline? (-) // Задача 1505. Перекачка нефти 3 июл 2013 21:03 Yes. We can decrease flow on some pipeline( if the flow on some pipeline is greater zero ). And this operation is free!!! =) Programmer WA 6. What is wrong? // Задача 1505. Перекачка нефти 16 май 2010 14:35 Alex Tolstov (Vologda STU) WA31 [1] // Задача 1505. Перекачка нефти 16 сен 2009 13:15 Why? Alex Tolstov (Vologda STU) Re: WA31 // Задача 1505. Перекачка нефти 25 сен 2009 01:05 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?? Slobodan Clarification request [1] // Задача 1505. Перекачка нефти 13 июн 2008 05:24 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. Chmel_Tolstiy Re: Clarification request // Задача 1505. Перекачка нефти 6 июл 2008 21:22 read carefully what "d" means. Lomir WA 26 [1] // Задача 1505. Перекачка нефти 6 ноя 2007 03:18 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? Fox Re: WA 26 // Задача 1505. Перекачка нефти 12 апр 2008 18:36 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! pperm Test #6 incorrect. [1] // Задача 1505. Перекачка нефти 18 сен 2007 00:47 In test#6 from station N oil is transported to other station. Edited by author 18.09.2007 00:48 Sandro (USU) Re: Test #6 incorrect. // Задача 1505. Перекачка нефти 18 сен 2007 01:24 Test #6 is correct, read the problem statement more carefully. it4.kp Clarification request [5] // Задача 1505. Перекачка нефти 6 янв 2007 23:54 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 ??? Vedernikoff Sergey Re: Clarification request [4] // Задача 1505. Перекачка нефти 11 янв 2007 20:46 How can it be equal to 0? I think correct answer is: 1 2 3. 4 0, 3 3. 4 5. . it4.kp Re: Clarification request [3] // Задача 1505. Перекачка нефти 12 янв 2007 12:59 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 Vedernikoff Sergey Re: Clarification request [2] // Задача 1505. Перекачка нефти 12 янв 2007 14:12 Hm, I think, you can be right... I'll try to implement it... Vedernikoff Sergey Re: Clarification request [1] // Задача 1505. Перекачка нефти 9 мар 2007 22:18 Yes, the idea described above is really right... svr Re: Clarification request // Задача 1505. Перекачка нефти 9 мар 2007 23:11 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. svr Deikstra [2] // Задача 1505. Перекачка нефти 9 дек 2006 22:37 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 Ilya Rasenstein (Lyceum #40) Re: Deikstra // Задача 1505. Перекачка нефти 6 янв 2007 14:02 Dijkstra - you should spell surnames properly Edited by author 06.01.2007 14:03 Vedernikoff Sergey Re: Deikstra // Задача 1505. Перекачка нефти 11 янв 2007 20:51 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... Vedernikoff Sergey What is the... // Задача 1505. Перекачка нефти 11 янв 2007 14:54 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? TesterTest Memory limit exceeded for Test nr. 4 // Задача 1505. Перекачка нефти 31 дек 2006 01:07 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 Deftone Clarification request // Задача 1505. Перекачка нефти 7 ноя 2006 18:43 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? EfremovAleksei I don't understand rejudge! [2] // Задача 1505. Перекачка нефти 6 ноя 2006 23:11 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 Vladimir Yakovlev (USU) Re: I don't understand rejudge! [1] // Задача 1505. Перекачка нефти 6 ноя 2006 23:29 Your submission 1378260 has WA#6 because it didn't output all edges. I can send you this submission and simple fail-test. EfremovAleksei Re: I don't understand rejudge! // Задача 1505. Перекачка нефти 7 ноя 2006 14:58 Thanks! I thought, that only last submit was rejudged. White Bear, White Dew, White Clouds What should I output if N = 1? // Задача 1505. Перекачка нефти 28 окт 2006 18:03 And where does the oil come from? Station 1?
|