JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Maximum Flow tutorial Thanks _efer_ << PREV    [ 1 2 ]
 Re: Thanks _efer_ (response to post by _efer_) | Reply topic :minimum number of vertices to disconnect the graphquote :"This time we can't improve in the quadratic number of steps needed, because the first vertex may be in an optimum solution and by always considering it as the source we lose such a case. "I think this can be optimised based on the result . for the first source(1st iteraiton) if the iteration gives a result of one vertice, well and good . else , we consider a second source(2nd iteration)... We only have to continue if the best result so far > iteration no.is my point valid?
 Re: Thanks _efer_ (response to post by smartnut007) | Reply Yes, I think you are right and here it is a proof: let's suppose the optimum solution is composed of vertices x_1, x_2, ..., x_k and let's suppose for the sake of contradiction that this solution can only be found at a step s > k + 1 (and contradict with your observation) then you must have that vertices 1, 2, ..., s - 1 are part of the solution (the ones you tried so far), otherwise you would have been able to find this solution earlier. Thus, you must have k >= s - 1 which implies k + 1 >= s, a contradiction.Anyway this won't improve in the quadratic number of steps. Consider the case of a complete graph, in which you have an edge between every two vertices.
 Re: Thanks _efer_ (response to post by aussie) | Reply +1. Excellent article!
 Re: Thanks _efer_ (response to post by _efer_) | Reply hey, I was just curious what you generate the graphics with? It's very pretty!
 Re: Thanks _efer_ (response to post by Larry) | Reply See above, Corel Draw 12
 Re: Thanks _efer_ (response to post by _efer_) | Reply In section 2, I did not understand why in figure 9 the rightmost edge of the "after" network is marked with capacity 11 instead of 7 as we have to add 2 to each edge capacity.
 Re: Thanks _efer_ (response to post by black.phoenix) | Reply The text says "add 1", so what _efer_ probably meant when he said "take T = 2" is that he's going to multiply all capacities by 2, then add 1.
 Re: Thanks _efer_ (response to post by _efer_) | Reply One more question. That DFS given in the problem RookAttack would find as a result 2 instead of 3 returned by the BFS code for find_path(), wouldn't it? It checks for a new column if it wasn't visited, visit it and mark it as visited, terminating the function call. It does not try other columns anymore because it does not uncheck the visited array and returns as soon as a new match was found. So row 0 would match column 1, row 1 would match column 0 but row 2 would not match any columns, resulting in 2 rooks placed instead of the maximum of 3 rooks.Maybe I understood the DFS code wrongly. Could anybody explain how it works?
 Forums Tutorial Discussions Maximum Flow tutorial Thanks _efer_ Previous Thread  |  Next Thread << PREV    [ 1 2 ]