Problem Link : http://codeforces.com/contest/546/problem/E

__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 a
_{i}. - Make a sink and second group of vertices in the same way, but use bi except for a
_{i}. - If there is a road between cities i and j or i = j. Make two edges, first should be connecting i
^{th}vertex from first group, and j^{th}vertex from second group, and has infinity capacity. Second should be similar, but connect j^{th}from first group and i^{th}from second group. - Then find a maxflow, in any complexity.
- If maxflow is equal to sum of a
_{i}and is equal to sum of b_{i}, 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**

Advertisements