結果

問題 No.763 Noelちゃんと木遊び
ユーザー drken1215drken1215
提出日時 2018-02-22 14:26:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,806 bytes
コンパイル時間 858 ms
コンパイル使用メモリ 78,404 KB
実行使用メモリ 22,676 KB
最終ジャッジ日時 2024-04-24 11:57:01
合計ジャッジ時間 3,809 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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] << ", ";
			}
		}
		return s;
	}
};

Graph G;

static int L = 0;     // ここに左ノードの使いたい頂点数をセット
static bool seen[MAX_L];
static bool matched[MAX_L];
static int level[MAX_L];
static 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 (flag == 0) ++L;
	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);

		/* 最大マッチングを求める */
		int max_matching = Hopcroft_Karp(G);

		/* N - 最大マッチング */
		cout << N - max_matching << endl;
}
0