SRM 640

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16083

Easy
Kruskalやるだけなんだけど貼るの遅かった…もうちょっとちゃんと整備します。

struct ChristmasTreeDecoration {
  vector<int> col;
  vector<int> x;
  vector<int> y;
  int solve(vector<int> _col, vector<int> _x, vector<int> _y) {
    col = _col, x = _x, y = _y;
	N = sz(col);
	init(N);
	E = 0;
	rep(i, 0, sz(x)) {
		int a = x[i] - 1, b = y[i] - 1;
		if(col[a] == col[b]) add_edge(a, b, 1);
		else add_edge(a, b, 0);
	}
    return kruskal();
  }
};

12 minutes 58 secs。

Medium
点の集合uとvの間にフローを流すことを考えます
uの部分集合u'と対応する集合v'をΓ(u')とします。
フローを流すと|u'|-|Γ(u')|が最大となるu'を求めることができます。(|u'|-|Γ(u')|=|u|-{|u-u'|+Γ(u')}で中カッコ内は最小カット問題にほかならないから)
逆に考えると、最大マッチングがcだとすると、|u'|-|Γ(u')| = a - cとなるので、
u'からは辺が|Γ(u')|=|u'|-a+c本引け、u - u'からはb本引けます。よって引ける辺は
|u'|^2 - (|u|+|v|-c)|u'| + |u||v|となります。また次数の条件より
|u| + d - c <= |u'| <= |u| - dを満たしている必要があります。あとは二次関数の最大値問題になるので解けます。

Hallの結婚定理とか残余グラフの話を少し忘れていましたね。

struct MaximumBipartiteMatchingProblem {
  int n1;
  int n2;
  int ans;
  int d;
  ll a, b, c;
  ll f(ll k) {
	  return k * k - (a + b - c) * k + a * b;
  }
  long long solve(int _n1, int _n2, int _ans, int _d) {
    n1 = _n1, n2 = _n2, ans = _ans, d = _d;
	a = n1; b = n2; c = ans;
	if(c == min(a, b)) return a * b;
	else if(a + d - c  <= a - d) {
		ll s1 = f(a + d - c);
		ll s2 = f(a - d);
		ll s3 = -1;
		if(a + d - c <= (a + b - c) / 2 && (a + b - c) / 2 <= a - d) {
			s3 = f((a + b - c) / 2);
		}
		if(a + d - c <= (a + b - c + 1) / 2 && (a + b - c + 1) / 2 <= a - d) {
			s3 = f((a + b - c + 1) / 2);
		}
		return max(max(s1, s2), s3);
	}
    else return -1;
  }
};

61 minutes 36 secs。でもいろいろ調べてやった割にはまあまあ速く通せたかな。