PROBLEM LINK:
Setter- Arjun Arul _/\_
Tester- Arjun Arul _/\_ , Animesh Fatehpuria
Editorialist- Abhishek Pandey
DIFFICULTY:
MEDIUM-HARD
PRE-REQUISITES:
Mincut-Maxflow Algorithm (especially Cycle Cancelling Algorithm ), Bellman Ford Algorithm
These pre-requisites are the basic requirements which must be sufficed before proceeding next. Hence, make sure you have an idea about what above mentioned things are :).
PROBLEM:
For a directed graph of N nodes, you can remove some edges. For each node, you must make outdegree-indegree=0. (i.e. Outdegree should be equal to indegree for each node.)
QUICK EXPLANATION:
The most important step to solve this problem is to identify it to be a min-cut max-flow problem. Once you do so, we will construct our graph in this fashion-
- Since we can do nothing about vital edges, we note their effect on degree and discard them. We then take input about non-vital edges in similar fashion, but we dont discard them.
- For each node with Outdegree>Indegree, we give an edge from source to that node with capacity= OutDegree-Indegree ,cost=0.
- For each node with Indegree>Outdegree, we give an edge from that node to sink with capacity=Indegree-Outdegree, cost=0.
- We make graph out of non-vital edges. Each such edge has cost=capacity=1.
- Now we apply the standard min-cut max-flow algorithms, with maximum flow =(OutDegree+Indegree)/2 [Outdegree=Excess OutDegree, Indegree= Excess Indegree]
- If maximum flow is achievable, we print the cost, which is edges cut, else we print -1.
EXPLANATION:
I first hope that you guys went through the pre-requisite links. If not, please do so, its not too late yet. 
. At any step, if you feel lost, or have any doubt related to implementation, please open editorialist’s solution in another tab and have a look there as well .
The editorial is divided into following sections-
- Identifying this is a MinCut-MaxFlow question
- Constructing the Graph
- Deriving answer from it
1. Identifying this is a MinCut-MaxFlow question-
The following points should guide you in identifying such questions-
- Low constraints so that a O(VE) or O(V{E}^{2}) &etc. algorithm passes.
- Take “Excess Indegree/Outdegree” as required flow which must pass through a node, Combined with need of minimum cuts/removal of edges, we can see it as a MinCut-MaxFlow algorithm.
2. Constructing the Graph-
This section will take a good portion of editorial, as this part is not intuitive and hence deserves explanation.
a. Are Vital edges really vital for the solution?
First, we must analyze the input carefully. We see that the vital edges are not important to us. Why? To answer that, we must see what exactly are we taking as “flow”. I took flow to be “edges cut in a path to satisfy Outdegree=Indegree relation” . In this sense, we can really not have a “flow” through vital edges as we cannot cut them. (The algorithm in our solution “cuts” the edges in path where flow is happening.) Hence, we do nothing but note the effect of vital edges on degree of nodes.
b. What about non-vital edges?
We can cut the non-vital edges. Each edge cut will reduce outdegree of one node and indegree of another by 1. Hence, cost and capacity of these edges should be 1. We follow typical steps to make a graph from them.
c. What about source and sink?
We add our own 2 nodes as Source and Sink. My solution follows 1-based indexing, hence I used Node 0 and Node (N+1) as source and sink respectively. We used the convention that nodes will have “Positive Outdegree and Negative Indegree” [Outgoing edges contribute +1, incoming contribute -1] . You can use your own convention, but make sure to change other things accordingly!
For each Node i with excess OutDegree, we add an edge from source to that Node i, with cost=0 [Since this edge should not affect answer] and capacity= |Excess Degree|. For each Node i with excess indegree, we add an edge from that Node i to sink, with cost=0 and capacity= |Excess Degree|.
3. Deriving the answer from this graph-
Before proceeding further, make sure to be well versed with the reverse graph theory in the MinCut-MaxFlow link I provided.
a. When will answer exist?
Firstly, it should be intuitive that for a valid solution, Total amount of Excess Outdegree = Total Amount of Excess Indegree. If this is not the case, the answer is -1. Why is this happening though?
Click to view
This is because we cannot “Create” any flow, but direct it from excess (outdegree) to deficit (indegree). Each edge will change outdegree of one node and indegree of another, so if their excesses are unequal, we cannot balance them.
b. What is the value of MaxFlow?
Follow the reasoning above. Since all we are doing is directing flow from “excess to deficit”. (A very good analogy is to take Excess Outdegree nodes having positive potential, Excess Indegree nodes with negative potential, and flow as current.)
Each edge has capacity 1, will satisfy outdegree of one node and indegree of another. Hence the required flow will be Flow=(|Excess Outdegree|+|Excess Indegree|)/2 .
Q- Can you use my inference in part a. to simply the above equation?
c. What do we actually do?
We need to have flow in our network equal to maxflow. If this cannot be achieved, then the answer does not exist. Recall from the reverse graph section of pre-requisites, that in condition of maxflow, source will not be connected to sink. (In real graph terms, it means there is no path with flow capacity>0 connecting sink and source. i.e. all paths are being used to their fullest). We will use this later.
While we dont get our flow equal to required maxflow , we find an augmenting path from source to sink and allow “flow” through the path. (i.e. we deduct flow-occuring through path from capacity of each involved edge) and compute cost. If we can reach the maxflow, we break out and give the current cost (i.e. edges cut) as the answer.
But…What if we cannot find a path from source to sink?
(Answer is in tab below, try to answer on your own first).
Click to view
Recall from reverse graph section (in pre-requsites,mincut maxcut algorithm) that in condition of maximum flow through network, source is disconnected from sink. Meaning, there is no path which can carry any more flow to sink from source.
If this is not equal to maxflow needed, it means that we cannot achieve it by just removing non-vital edges, we will need to remove vital edges as well, which is not allowed. Hence, answer is -1 for such cases.
Once we get final flow through the network, and the cost, we can easily see what the answer is.
SOLUTION:
CHEF VIJJU’S CORNER:
1.We used Bellman Ford because of possible negative weight (cost) in edges. Can we use Dijkstra’s algorithm here? Some people used both! “If no negative edge, use Dijkstra, else Bellman Ford”.
2.A very common question is “For graphs with negative edges, we just add a positive constant K to all weights and apply Dijkstra and then subtract similarly from answer.” . Is this procedure correct? How does it interact with the negative cycle anomaly in such graphs?
3.Is Dijkstra completely inapplicable to all graphs with any negative weight edges?
4.After going through editorialist’s solution, how many of you want to kill and burn him on a stake for not making a function/constructor to make/add edges? 