Блог пользователя Madiyar

acm.sgu.ru 206
Автор Madiyar, 13 лет назад, По-русски

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] ?


 
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
you need to modify some of MST algorithms, Prim's or Kruscals's. MST - Minimal spanning tree, i see how this ploblem can be solved, but i think it would be ineresting for you to solve it by itself.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    You have answered in Russian interface. And I doubt it can be solved using either Prim's or Kruskal's algorithm.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Am I understood right, we needn't linear programming here )) We just need to to modify MST)
    → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Ok thank you very much))))) 
→ Ответить
13 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.
    → Ответить