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

What is wrong in this logic?
Автор root8950, 9 лет назад, По-английски

I am new to max flow type questions. In this problem, http://mirror.codeforces.com/contest/653/problem/D , if I use any max flow algorithm and find flow from starting node( ie 1 ) to its all neighbors.
Lets take an example if from node 1, four other nodes are connected with capacities 4 , 5 , 6 , 7 respectively and after applying max flow algorithm, say the flow comes out to be 3 , 5 , 6 , 6 (if we consider max flow) (these values are arbitrary here.)
And then I apply binary search. In binary search step, I am finding the total weight that all bears will carry and then dividing it by number of bears ( say I obtain k=2, the weight each bear will carry). Now if using the flows obtained earlier ie 3 , 5 , 6 , 6. I try to allocate bears (that will be 1 , 2 , 3 , 3) and see if allocation is possible or not. (by comparing the bears I allocated here 1+2+3+3 = 9 with bears I originally had)
Is this approach correct?

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

No, algorithm starts with binary search (0 to 10^6). For each value (carry weight per bear) to test — graph is constructed, where each node represents how many bears can go through that edge (capacity/weight -> integral number of bears). Running Max-Flow on such graph will return number of bears can go through. Back to binary search, you need to find carry weight per bear, that yields more or equal number of bears you need.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Yeah. I know this approach and even used it :) . I was just asking where the approach, I pointed above will fail?

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by root8950 (previous revision, new revision, compare).

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I used the same approach and came to know after the contest for a counter case as follows :

Consider the Directed Graph as 

1->2 with weight = 4
2->3 with weight = 2
2->4 with weight = 2
3->5 with weight = 2
4->5 with weight = 2

Max Flow : 4

If you consider the residual graph edge neighbour to node 1 after finding out flow then it becomes 0(as max flow is 4), and you try to obtain the answer by considering 4 bears and dividing by the binary_searched weight , but in actual you were never supposed to take weight more than any edge weight lying in the path, which in this case is 2 .

→ Ответить