はまやんはまやんはまやん

hamayanhamayan's blog

Making Pair [ACPC2017 Day2 I]

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);
    }
}