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。でもいろいろ調べてやった割にはまあまあ速く通せたかな。