Network Flow with constraint of equal flows on given list of edges.
source link: https://codeforces.com/blog/entry/110260
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
I have some network , and for edges , ... , there is constraint that flow on these edges should be always equal to each other: . Given this constraint I want to find max flow on . is network with around 10k edges and I have around 1-5 minutes time limit. Any ideas, papers, problems?
|
59 minutes ago, # | This is an interesting problem and it has been studied before. The paper by Srinivasan and Thompson (1972) solves it : https://onlinelibrary.wiley.com/doi/epdf/10.1002/nav.3800190202 This is how to reduce the problem to the paper above. Start by removing the edges from the graph, but remember both the minimum capacity of those edges, and the difference between the number of edges with as head and those with as tail. Also add an edge between tap and source of infinite capacity and cost -1 (all other edges are of cost -1). Then you can notice that we want to solve the following problem for all between 0 and : If you can solve that LP for all between 0 and then you win, the flow is simply the flow on edge from tap to source. The book Network Flows : theory, algorithms and applications contains this problem as an exercice (11.51), I suggest reading both the exercice and either the corresponding chapter, or https://codeforces.com/blog/entry/94190 to better understand how to solve this. |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK