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.

Solution

---