MaximumBipartiteMatchingProblem
SRM 640 · 2014-08-25 · by dreamoon
Problem Statement
Given an undirected graph, a matching is a subset of its edges such that no two edges share a common vertex. A maximum matching is a matching such that the number of edges it contains is as large as possible.
We are now interested in graphs that have the following properties:
- The graph G is a simple undirected graph.
- G is bipartite with partition sizes n1 and n2. In other words, we can split its vertices into two disjoint sets, A and B, such that the size of A is n1, the size of B is n2, and each edge of the graph connects a vertex in A and a vertex in B.
- The size of the maximum matching in G is exactly ans.
- The degree of each vertex is at least d.
If there are no such graphs, return -1. Otherwise, return the largest possible number of edges in such a graph.
Constraints
- n1 and n2 will be between 1 and 1,000,000,000(10^9), inclusive.
- ans and d will between 1 and min(n1,n2), inclusive.
3 3 2 1 Returns: 5
One optimal graph is shown in the picture below. The red vertices form one partition, the blue ones form the other partition.
3 3 1 1 Returns: -1
5 10 5 2 Returns: 50
100000000 87654321 12345678 54321 Returns: 1233229491567444
1000000000 1000000000 1000000000 1000000000 Returns: 1000000000000000000
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MaximumBipartiteMatchingProblem with a public method long long solve(int n1, int n2, int ans, int d) · 63 test cases · 2 s / 256 MB per case