#863709 (C++14) No.2286 Join Hands

• 問題: No.2286 Join Hands
• ユーザー: Jaehyun Koo
• 提出日時: 2023-04-28 21:45:21
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 60 ms / 2,000 ms
• コード長: 2,534 bytes
• コンパイル時間: 1,999 ms
• コンパイル使用メモリ: 183,132 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-28 23:24:04
• 合計ジャッジ時間: 4,320 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	6 ms; 5,376 KB
testcase_09	AC	6 ms; 5,376 KB
testcase_10	AC	13 ms; 5,376 KB
testcase_11	AC	15 ms; 5,376 KB
testcase_12	AC	13 ms; 5,376 KB
testcase_13	AC	11 ms; 5,376 KB
testcase_14	AC	17 ms; 5,376 KB
testcase_15	AC	16 ms; 5,376 KB
testcase_16	AC	17 ms; 5,376 KB
testcase_17	AC	6 ms; 5,376 KB
testcase_18	AC	22 ms; 5,376 KB
testcase_19	AC	33 ms; 5,376 KB
testcase_20	AC	27 ms; 5,376 KB
testcase_21	AC	22 ms; 5,376 KB
testcase_22	AC	30 ms; 5,376 KB
testcase_23	AC	39 ms; 5,376 KB
testcase_24	AC	24 ms; 5,376 KB
testcase_25	AC	36 ms; 5,376 KB
testcase_26	AC	40 ms; 5,376 KB
testcase_27	AC	38 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB
testcase_30	AC	2 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	2 ms; 5,376 KB
testcase_33	AC	3 ms; 5,376 KB
testcase_34	AC	2 ms; 5,376 KB
testcase_35	AC	2 ms; 5,376 KB
testcase_36	AC	2 ms; 5,376 KB
testcase_37	AC	2 ms; 5,376 KB
testcase_38	AC	2 ms; 5,376 KB
testcase_39	AC	2 ms; 5,376 KB
testcase_40	AC	2 ms; 5,376 KB
testcase_41	AC	2 ms; 5,376 KB
testcase_42	AC	3 ms; 5,376 KB
testcase_43	AC	2 ms; 5,376 KB
testcase_44	AC	2 ms; 5,376 KB
testcase_45	AC	2 ms; 5,376 KB
testcase_46	AC	2 ms; 5,376 KB
testcase_47	AC	7 ms; 5,376 KB
testcase_48	AC	8 ms; 5,376 KB
testcase_49	AC	8 ms; 5,376 KB
testcase_50	AC	8 ms; 5,376 KB
testcase_51	AC	55 ms; 5,376 KB
testcase_52	AC	19 ms; 5,376 KB
testcase_53	AC	9 ms; 5,376 KB
testcase_54	AC	6 ms; 5,376 KB
testcase_55	AC	7 ms; 5,376 KB
testcase_56	AC	7 ms; 5,376 KB
testcase_57	AC	7 ms; 5,376 KB
testcase_58	AC	7 ms; 5,376 KB
testcase_59	AC	7 ms; 5,376 KB
testcase_60	AC	60 ms; 5,376 KB

ソースコード

#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";
}