qinpengfei's blog

uva 10122 - Mysterious Mountain
By qinpengfei, 16 years ago, In English


who can help me ?
I use “maxflow and bsearch” to solve this problem ,but I get the wrong. I don't know where is worng in my code. I need you help me. Thank you very much.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I've solved this problem using binary search on answer and maximum matching algorithm (Kuhn algorithm) for checking if it possible to create perfect matching with this time.

I think you probably have error with checking line from point x on the bottom with point on top of some mountain corresponding to the condition - (obviously, no part of the path that he follows can be OVER the mountain - they can't fly).

→ Reply
16 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

According to statement:

"For every person i, he is planing to go left/right to some place (x,0) (where x is an integer).

 then climb directly to the destination along a straight line."


It means that any person can move to any integer (x, 0) and then go directly to the top of chosen mountain along a straight line. And on this line there should be no point over the surface of mountain. 

→ Reply
  • 16 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    However, I don't know how to deal with this sitution, can you give a algorithm to handle this sitution? 

    → Reply
    • 16 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      The simpliest approach is for every top of mountain and each human try all integer points and check if here exists way according to the statement (checking all other vertexes) and take minimum from all of them. It's pretty bad complexity but I've used it and get AC.
      → Reply