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 Network flow algorithm?
 Network flow algorithm? | Reply Hi,I have got a problem like this:We are given a bipartite graph. For e.g.A1 B1A2 B2A3 B3A4And here is the adjacency list representation (assume graph is bidirectional)B1 -> A2, A3B2 -> A2, A3, A4B3 -> A1Final result should be that all nodes in the left side (As) have exactly 1 incoming edge and at the same time - we need to minimize the maximum number of edges that need to go out of individual Bs nodes. In this case the answer would be:B3 can connect to A1B2 can connect to A2, A4B1 can connect to A3So here the maximum number of edges that need to out of a single Bs node is 2. We cannot cover all As and at the same time have a B node not having 2 edges going out of it to cover As.Another example:A1 B1A2 B2A3 B3A4 B4B1 -> A1, A2, A3B2 -> A1, A2, A3, A4B3 -> A1, A2, A3B4 -> A1, A2, A3In this case the answer would be:B1 can connect to A1B2 can connect to A4B3 can connect to A3B2 can connect to A2This way we will cover all the As exactly once and at the same time we have minimized the maximum number of edges that need to go out of individual B's. So here the maximum number of edges that need to out of a single Bs node is 1.Another example:A1 B1A2 B2A3 B3A4A5A6B1 -> A6B2 -> A1, A2, A3, A4, A5B3 ->In this case the answer would be 5 i.e. the maximum number of edges that need to go out of a single Bs is 5. Can't do less than that.I have implemented basic ford fulkerson algorithm and I know this is also network flow but don't know how to relate to it.It will be great if someone can give some hint about the graph.Thanks
 Re: Network flow algorithm? (response to post by vsha041) | Reply Well I found it anyway - It can be done by having a source node connected to all A's and connecting all B's to a sink node. Then give the edge weight of 1 to all nodes from source to A's - find the max flow - if its not equal to maximum of A's that can be covered - increase those edge capacities by 1 - keep doing till you reach the maximum of A's that can be covered. Push - Relabel will give (number of A's that be covered) * n^3 performance which is quite fast.
 Forums Tutorial Discussions Maximum Flow tutorial Network flow algorithm? Previous Thread  |  Next Thread