Indian Computing Olympiad

Network Flows→Going to School

Father has two children who keep fighting. When they go to school, they want to take routes on which they do not both have to travel on the same road. Can the father send them to the same school?

Example

             ->3
            /   \
           /     \
          /--->2------------>6--
         /      \  \            \
        /        \  \            \
       H          ---->4        ---->S
        \        /      \      / /
         \      /        \    / /
          ---->1          -->5 /
                \             /
                 -------------
      

In general, are there k edge-disjoint paths from s to t? The paths may meet at vertices.

Use max-flow. Put a capacity 1 on each edge. If max flow > 2, there are at least 2 edge disjoint paths.

In general, the max flow gives the maximum number of edge disjoint paths.

(The max flow-min cut theorem for 0/1 flows is called Menger's Theorem.)

Also, observe that since the flow increases with each iteration, we may be able to stop before the max flow is reached. For instance, if we are asked whether there are at least K edge-disjoint paths, we can stop when we attain a flow of K.

---