ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1505. Oil Transfer

WA31
Posted by Alex Tolstov (Vologda STU) 16 Sep 2009 13:15
Why?
Re: WA31
Posted by Alex Tolstov (Vologda STU) 25 Sep 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??