MaximumBipartiteMatchingProblem

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.

Definition

Class:: MaximumBipartiteMatchingProblem
Method:: solve
Parameters:: int, int, int, int
Returns:: long
Method signature:: long solve(int n1, int n2, int ans, int d)
(be sure your method is public)

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.

Examples

```
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

Returns: 1233229491567444

1000000000

1000000000

1000000000

1000000000

Returns: 1000000000000000000

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.