CF: 546-D2-E-Soldier and Traveling

Problem Link:
Solution Idea:

  • We can solve this problem by using maxflow. So at first make a source
  • Make the first group of vertices consisting of n vertices, each of them for one city.
  • Connect a source with ith vertex in the first group with an edge that has capacity ai.
  • Make a sink and second group of vertices in the same way, but use bi except for ai.
  • If there is a road between cities i and j or i = j. Make two edges, first should be connecting ith vertex from the first group, and jth vertex from the second group, and has infinity capacity. The second should be similar but connect jth from the first group and ith from the second group.
  • Then find a maxflow, in any complexity.
  • If maxflow is equal to the sum of ai and is equal to the sum of bi, then there exists an answer. How can we get it? We just have to check how many units are we pushing through edge connecting two vertices from different groups.

Using Dinitz Maxflow

Using Ford Fulkerson Maxflow