http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=I
解法
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2538411&cid=ACPC2017Day2
あるマッチングから、増加路を探すことでより良いマッチングを探すことができる。
このサイトに条件が書いてある
マッチング M について以下を満たすとき道 P は増加道であるという。
- P の出発点と到着点がマッチングの端点でない
- 交互路である(M に含まれていない枝と含まれている枝を交互に使う)
これを探すにはBFSで探していけばいい。
新しく頂点が追加されたらBFSで増加路を探し、それがあればマッチング数を増やしていく。
int N; vector<int> E[5010]; int f[5010][5010]; int ma[5010]; //-------------------------------------------------------------------------------------------------- void _main() { cin >> N; int ans = 0; rep(i, 1, N + 1) { int P; cin >> P; E[i].push_back(P); E[P].push_back(i); queue < tuple<int, int, vector<int>>> que; que.push(make_tuple( i, -1, vector<int>{i} )); vector<int> zouka = {i}; while (!que.empty()) { int cu, pa; vector<int> v; tie(cu, pa, v) = que.front(); que.pop(); if (0 < v.size() && v.size() % 2 == 0 && !ma[v.front()] && !ma[v.back()]) { zouka = v; break; } int type = 0; if (pa < 0) type = 1; else type = f[cu][pa]; fore(to, E[cu]) if (pa != to && f[cu][to] != type) { v.push_back(to); que.push(make_tuple( to, cu, v )); v.pop_back(); } } if (zouka.size() % 2 == 0 && !ma[zouka.front()] && !ma[zouka.back()]) { ans++; int n = zouka.size(); rep(i, 0, n - 1) { int a = zouka[i], b = zouka[i + 1]; //printf("%d -> ", f[a][b]); f[a][b] = 1 - f[a][b]; f[b][a] = 1 - f[b][a]; } //printf("\n"); ma[zouka.front()] = 1; ma[zouka.back()] = 1; } printf("%d\n", ans); } }