root8950's blog

What is wrong in this logic?
By root8950, 9 years ago, In English

I am new to max flow type questions. In this problem, http://codeforces.net/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?

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 .

→ Reply