結果

問題 No.2286 Join Hands
ユーザー Jaehyun KooJaehyun Koo
提出日時 2023-04-28 21:45:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 2,534 bytes
コンパイル時間 2,079 ms
コンパイル使用メモリ 182,408 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 20:44:14
合計ジャッジ時間 3,891 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXN = 10005 + 1;

struct gm {
	// 1-based Vertex index
	int vis[MAXN], par[MAXN], orig[MAXN], match[MAXN], aux[MAXN], t, N;
	vector<int> conn[MAXN];
	queue<int> Q;
	void addEdge(int u, int v) {
		u++;
		v++;
		conn[u].push_back(v);
		conn[v].push_back(u);
	}
	void init(int n) {
		N = n;
		t = 0;
		for (int i = 0; i <= n; ++i) {
			conn[i].clear();
			match[i] = aux[i] = par[i] = 0;
		}
	}
	void augment(int u, int v) {
		int pv = v, nv;
		do {
			pv = par[v];
			nv = match[pv];
			match[v] = pv;
			match[pv] = v;
			v = nv;
		} while (u != pv);
	}
	int lca(int v, int w) {
		++t;
		while (true) {
			if (v) {
				if (aux[v] == t)
					return v;
				aux[v] = t;
				v = orig[par[match[v]]];
			}
			swap(v, w);
		}
	}
	void blossom(int v, int w, int a) {
		while (orig[v] != a) {
			par[v] = w;
			w = match[v];
			if (vis[w] == 1)
				Q.push(w), vis[w] = 0;
			orig[v] = orig[w] = a;
			v = par[w];
		}
	}
	bool bfs(int u) {
		fill(vis + 1, vis + 1 + N, -1);
		iota(orig + 1, orig + N + 1, 1);
		Q = queue<int>();
		Q.push(u);
		vis[u] = 0;
		while (!Q.empty()) {
			int v = Q.front();
			Q.pop();
			for (int x : conn[v]) {
				if (vis[x] == -1) {
					par[x] = v;
					vis[x] = 1;
					if (!match[x])
						return augment(u, x), true;
					Q.push(match[x]);
					vis[match[x]] = 0;
				} else if (vis[x] == 0 && orig[v] != orig[x]) {
					int a = lca(orig[v], orig[x]);
					blossom(x, v, a);
					blossom(v, x, a);
				}
			}
		}
		return false;
	}
	int Match() {
		int ans = 0;
		// find random matching (not necessary, constant improvement)
		vector<int> V(N - 1);
		iota(V.begin(), V.end(), 1);
		shuffle(V.begin(), V.end(), mt19937(0x94949));
		for (auto x : V)
			if (!match[x]) {
				for (auto y : conn[x])
					if (!match[y]) {
						match[x] = y, match[y] = x;
						++ans;
						break;
					}
			}
		for (int i = 1; i <= N; ++i)
			if (!match[i] && bfs(i))
				++ans;
		return ans;
	}
} gm;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin >> n >> m;
	gm.init(2 * n);
	set<int> isol;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		gm.addEdge(u, v);
		gm.addEdge(u, v + n);
		gm.addEdge(u + n, v);
		gm.addEdge(u + n, v + n);
		isol.insert(u);
		isol.insert(v);
	}
	int mtch = gm.Match();
	if (mtch == n - 1 && sz(isol) == n - 1)
		mtch--;
	cout << mtch * 2 - n << "\n";
}
0