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
54321
Returns: 1233229491567444
1000000000
1000000000
1000000000
1000000000
Returns: 1000000000000000000
90539234
898807697
12574826
469525
Returns: 10917164405693622
713373279
551720264
410052993
164292676
Returns: 225585821627817615
486850342
565932541
54688090
88117565
Returns: -1
216926447
320144403
115936424
190377233
Returns: -1
395975276
31685180
26810262
887834
Returns: 10269756949049296
413487987
12165759
5418358
854480
Returns: 1893604382410466
768529111
291075431
149430089
26859370
Returns: 98725096114052249
182307187
870999941
69540885
35960203
Returns: -1
387959455
195095712
154065142
41556586
Returns: 47080798319406396
394851796
300139294
202432194
55766981
Returns: 66469808922892009
240618126
931564552
21499363
93601905
Returns: -1
509806102
740450199
459926682
105664903
Returns: 278748780560639690
286017275
98696879
26406676
49848966
Returns: -1
176607183
82752090
27402196
3235768
Returns: 4457534382610740
904142970
86684181
39304426
18206720
Returns: 20269457149138820
860402
455833282
74748
21268
Returns: 24395125538456
308790490
807572025
267585932
92661349
Returns: 153668395243319118
972341219
546918581
48970667
2086432
Returns: 46630761872375937
148521511
60035903
51165306
10453719
Returns: 6248557385779161
720481901
95223838
65259080
13817042
Returns: 37667992298989838
660611782
403670583
172135911
55896922
Returns: 92855387051322066
851892999
711940980
312554503
23190277
Returns: 256307030269474632
982421233
121893014
85182342
71235380
Returns: -1
452565020
831779575
145568654
3121746
Returns: 119452538571967652
141583628
830405197
55864215
16636972
Returns: 34277406762448091
925524264
885301070
299888139
539839687
Returns: -1
329344953
553910449
65098224
174357015
Returns: -1
954131434
893604256
645194755
297839051
Returns: 494117146303403688
931092880
432819339
430789645
193327524
Returns: 258867217384266712
839487479
899810406
61991923
23988299
Returns: 53422290698323989
234501084
325785612
123307716
44239543
Returns: 32635554080326549
889720185
566181255
240329589
142334353
Returns: -1
391240928
384970101
214028698
3468515
Returns: 82984704813501594
955931618
609335164
544971155
186230571
Returns: 389599838628290092
810432354
864149426
797803289
184283067
Returns: 566460719295161416
998202313
74659979
52386537
14063805
Returns: 38764879678923951
769787021
153307204
81308389
7485512
Returns: 57422873451049841
760950112
923389025
588539545
11155741
Returns: 535197686014725328
225566324
812960286
210555922
89820501
Returns: 107569066614232809
167042841
262645132
86780941
38701392
Returns: 17231904490907932
813666486
215935339
190082031
3179227
Returns: 152168848773377189
749287539
822961065
115903729
35631181
Returns: 89898975828377991
380798481
433393244
315727771
111100193
Returns: 108256831165567311
752385804
868258881
633161202
56260064
Returns: 510772315067685202
112739046
931193182
36527063
56801338
Returns: -1
897243753
173383589
48476657
13432781
Returns: 33301185890238481
845132290
119162740
56964832
11117018
Returns: 39562511389324728
138794766
841714255
132339773
20538623
Returns: 94659033382824018
965112354
321019279
274830349
58421548
Returns: 214970313421207498
589232099
848122001
52958902
6159878
Returns: 43032603444891874
101
101
100
50
Returns: 7600
101
101
100
51
Returns: -1
102
102
101
50
Returns: 7752
102
102
101
51
Returns: -1
1
1000000000
1
1
Returns: 1000000000
1
1
1
1
Returns: 1
2
2
1
1
Returns: -1
15
18
1
2
Returns: -1