結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー drken1215
提出日時 2018-02-25 01:33:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 129 ms / 2,000 ms
コード長 3,275 bytes
コンパイル時間 735 ms
コンパイル使用メモリ 74,144 KB
実行使用メモリ 22,536 KB
最終ジャッジ日時 2025-03-22 10:32:14
合計ジャッジ時間 3,654 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 110000;
int N;
vector<int> tree[MAX];

/* Hopcroft-Karp の二部マッチング */
const int MAX_L = MAX;
const int MAX_R = MAX;

struct Graph {
    vector<int> adj[MAX_L];
    
    Graph() {}
    inline vector<int>& operator [] (int i) { return adj[i]; }
    void addedge(int from, int to) { adj[from].push_back(to); }
    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl;
        for (int i = 0; i < MAX_L; ++i) {
            if (G.adj[i].empty()) continue;
            s << i << " : ";
            for (int j = 0; j < G.adj[i].size(); ++j) {
                s << G.adj[i][j] << ", ";
            }
            s << endl;
        }
        return s;
    }
};

Graph G;

int L = MAX_L - 1;     // ここに左ノードの使いたい頂点数をセット
bool seen[MAX_L];
bool matched[MAX_L];
int level[MAX_L];
int matching[MAX_R];

void hobfs(Graph &G) {
    queue<int> que;
    for (int left = 0; left < L; ++left) {
        level[left] = -1;
        if (!matched[left]) {
            que.push(left);
            level[left] = 0;
        }
    }
    level[L] = L;
    while (!que.empty()) {
        int left = que.front();
        que.pop();
        for (int i = 0; i < G[left].size(); ++i) {
            int right = G[left][i];
            int next = matching[right];
            if (level[next] == -1) {
                level[next] = level[left] + 1;
                que.push(next);
            }
        }
    }
}

bool hodfs(Graph &G, int left) {
    if (left == L) return true;
    if (seen[left]) return false;
    seen[left] = true;
    for (int i = 0; i < G[left].size(); ++i) {
        int right = G[left][i];
        int next = matching[right];
        if (level[next] > level[left] && hodfs(G, next)) {
            matching[right] = left;
            return true;
        }
    }
    return false;
}

int Hopcroft_Karp(Graph &G) {
    for (int i = 0; i < MAX_R; ++i) matching[i] = L;
    memset(matched, 0, sizeof(matched));
    
    int res = 0;
    while (true) {
        hobfs(G);
        memset(seen, 0, sizeof(seen));
        bool finished = true;
        for (int left = 0; left < L; ++left) {
            if (!matched[left] && hodfs(G, left)) {
                matched[left] = true;
                ++res;
                finished = false;
            }
        }
        if (finished) break;
    }
    return res;
}



/* ツリーを二部グラフに */
void rec(int v, int flag, int p = -1) {
    if (p != -1) {
        if (flag == 0) {
            G.addedge(v, p);
        }
        else {
            G.addedge(p, v);
        }
    }
    for (auto ch : tree[v]) {
        if (ch == p) continue;
        rec(ch, 1 - flag, v);
    }
}



int main() {
    cin >> N;
    for (int i = 0; i < N-1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    
    /* ツリーは二部グラフなので「左」と「右」にわける */
    rec(0, 0);
    
    /* 最大マッチングを求める */
    L = N;
    int max_matching = Hopcroft_Karp(G);
    
    /* N - 最大マッチング */
    cout << N - max_matching << endl;
}
0