CF: 546-D2-E-Soldier and Traveling

Problem Link :
Solution Idea:

  • We can solve this problem using maxflow. So at first make a source
  • Make a first group of vertices consisting of n vertices, each of them for one city.
  • Connect a source with ith vertex in first group with 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 first group, and jth vertex from second group, and has infinity capacity. Second should be similar, but connect jth from first group and ith from second group.
  • Then find a maxflow, in any complexity.
  • If maxflow is equal to sum of ai and is equal to 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