TopCoder SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Problem Statement:
SRM 640 Div.1 550 - MaximumBipartiteMatchingProblem

Solution:
A very mathematical problem I guess, we will get to optimise a quadratic function. Firstly, take ans vertices from both n1 and n2, and match them like this:

ans pairs of vertices:

o o o o o  -> upper-end
| | | | |
o o o o o  -> lower-end

That means we have (n1-ans) unmatched vertices from the first set F, and (n2-ans) unmatched vertices from the second set S. We cannot match any of these unmatched vertices amongst themselves, because it will immediately increase the number of bipartite matching. So we can only match them with those ans paired vertices

 For each pair, we can only connect with either the upper or the lower end of the pair. Those from F must match to the lower-end, while those from S must match with the upper-end. It's easy to see that for each pair, we can't have both ends paired to other vertices from S or F at the same time, since it will add to the maximum bipartite matching. Hence we can separate the pairs in into two set P and Q, where P are those pairs whose lower-ends are matched with F, while Q are those pairs whose upper-ends are matched with S. Then to total number of edges is the sum of :
1. |P| * |P| (edges formed between upper-end and the lower-end of the pairs in P itself, which is OK)
2. similarly |Q|*|Q|
3. |P|*(n1-ans) (edges between lower-end in P and the edges in F)
4. similarly |Q|*(n2-ans)
5. finally |P| * |Q| (edges between the lower-ends of P and upper-ends of Q, which is also OK)

Furthermore, we also have |P| + |Q| = ans, so after some simplification we have:
f(|P|) = |P| * |P| + (n2 - n1 - ans) * |P| + ans * n1
which has a turning point at |P| = (ans + n1 - n2) / 2.
Depending on the position of the turning point, we can determine whether we want |P| as small as possible or as large as possible. There is a special case: if n1 or n2 is equal to ans, then the maximum edges is simply n1 * n2. Finally we need both |P| and |Q| to be at least D so that all vertices in F and S can have at least D degree. Therefore if ans is less than 2*|D|, there will be no answer.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

long long f(long long p, long long n1, long long n2, long long ans) {
 return p*p + (n2 - n1 - ans) * p + ans * n1;
}

class MaximumBipartiteMatchingProblem {
public:
 long long solve(int n1, int n2, int ans, int d) {
  long long ret = -1;
  if(ans == n1 || ans == n2) return 1LL*n1*n2;
  if(ans < 2*d) return -1;
  if(n1 < n2) swap(n1, n2);
  double tp = 1.0 * (ans + n1 - n2) / 2.0;
  if(tp <= 0) {
   ret = max(ret, f(ans - d, n1, n2, ans));
  } else {
   ret = max(ret, f(d, n1, n2, ans));
  }
  return ret;
 }
};