Given a bipartite graph with weighted vertices, each node $i$ has two values associated with it:
The cost of a matching is the sum of the weights of the two matched nodes. Find the min-cost max matching.
Ps. Two nodes can be matched multiple times.
The first line of the input is made of a three integer $n,m,k$ $(2 \leq n + m \leq 10^4$$,1 \leq k \leq 10^4)$, the number of nodes in the left sides, the number of nodes in the right sides, and the number of edges respectively.
The next $n + m$ lines contain $2$ integers each $match_i,weight_i$ $(1 \leq match_i \leq 10^4,1\leq weight_i \leq 10^9),$ the first $n$ rows are for the nodes on the left side, and the last $m$ rows are for the nodes on the right side.
The last $k$ lines contain two integers each $x,y$$(1\leq x \leq n, 1 \leq y \leq m)$.
Print two integers, the first being the max matching, and the second being the min-cost.
A maximum matching in this bipartite graph is the maximum number of pairs ($a,b$) such that $a$ is a node on the left side, $b$ is a node on the right side and there's an edge between $a$ and $b$, also for each node $i$, it should be present in the pairs at most $match_i$ times. Note that the same pair ($a, b$) can appear multiple times in a matching.
The cost of a matching is the sum of $weight_a + weight_b$ for all pairs in that matching. The min-cost max matching is the matching with the maximum number of pairs, if there are multiple matchings with the maximum number of pairs then it's the one with the minimum cost.
| Input | Output |
|---|---|
3 2 5 3 6 2 3 1 2 3 5 4 2 1 1 1 2 2 1 3 1 3 2 Copy
|
6 44 Copy
|
The main idea of the intended solution is to set the weight of the nodes to the edges between the source and the nodes on the left, and between the sink and the nodes on the right, then use classical Bellman-Ford min-cost maxflow, but use topological sort instead of Bellman-Ford.
Lemma: The back edges to the source and from the sink will never be used.
Proof: Min-cost maxflow never creates negative weight cycles, thus never going through the same node twice in the same path. This means that back edges to the source and the sink will never be used since these two nodes are in all valid paths without the use of back edges.
Another important observation is that the weights of all edges between the left and right are always zero.
Due to the aforementioned observations, we can do the following: