Madiyar's blog

acm.sgu.ru 206
By Madiyar, 13 years ago, translation, In English

http://acm.sgu.ru/problem.php?contest=0&problem=206


please , Help to solve this task

I reduced this task to linear programming, and linear programming to dual 

w[j] >= w[i] (where  j = n .. m  and i = 1 .. n-1 ) this is the least condition for minimality

and We must find x[i] (where i = 1..m) ,such that x[1] + x[2] + .. + x[m] is minimal

and conditions  are: 
w[j]+x[j] >= w[i] - x[i]

This equation is linear programming,  and dual form of this equation is the optimal match problem

so we can find sum of x[1]+x[2]+...+x[m], and how to find x[i] ?


 
  • Vote: I like it
  • +4
  • Vote: I do not like it

13 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I would try min cost - max flow. Sort the roads by cost. Make edges between each stoned road (that has a cost greater than road N-1 - let's call them A) and each country road (that has a cost lower than road N - let's call them B) . Let's say we have edge between stoned road i and country road j. Then cost(i,j)  is the difference between report cost and real cost, such that stoned road i will be chosen instead of country road j. There are at most 59 stoned road, so |A| < 60 and |B| = |A| thus simple O(n^4) algorithm works in time.



Edit: I am not sure if O(n^4) works, I think it should and in most cases it works, but implementing hungarian is not a bad thing. I'll have to try it.


Edit2: I assume you know, how to find the solution from the residual network.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry, my reply was to the post in the Russian interface, so you probably didn't see it. Here is an article in which O(N2logN) solution is described. There is also O(N3) solution in this article and I think it is sufficient for the given constraints.
    → Reply