We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I checked out a couple of solutions from the leaderboard and it seems that lot of them are using the following max-flow algorithm:
- we create a new graph where original vertices are duplicated (vertex i becomes 2*i and 2*i+1)
- if i and j vertices were connected in original graph then 2*i and 2*j+1 plus 2*j and 2*i+1 gets connected in new graph with capacity 1
- source vertex (S) is connected to each 2*i vertex with capacity min(T, degree)
- each 2*i+1 vertex is connected to target vertex (T) with capacity 1
- max-flow gives the answer
I was trying to come up with a similar flow-based solution but it's always seemed wrong. I realize that the above algorithm always gives the correct answer but I just cannot see why.
Crab Graphs
You are viewing a single comment's thread. Return to all comments →
I checked out a couple of solutions from the leaderboard and it seems that lot of them are using the following max-flow algorithm:
I was trying to come up with a similar flow-based solution but it's always seemed wrong. I realize that the above algorithm always gives the correct answer but I just cannot see why.
Could someone explain why this works? Thx!