OI 模板合集

更新日志

20220203 添加图论模块、稳定婚姻问题。

模板

图论

稳定婚姻问题

// 稳定婚姻匹配
// GS 算法
// 模板题 poj3487 
// 链接 : https://vjudge.net/problem/POJ-3487

int n, rk[30][30], po[30][30], cur[30], ans[30], mat[30];
map id;
char s[30], name_male[30][30], name_female[30][30];
queue q;

// n : 人数
// rk[i][j] : 男生 i 那里排名 j 的女生
// po[i][j] : 女生 i 那里男生 j 的排名
// id[s] : 名字为 s 的人的编号，区分男女
// cur[i] : 男生 i 当前尝试到他那里排名为 j 的女生
// mat[i] : 女生 i 当前匹配的男生
// ans[i] : 男生 i 最后匹配的女生

void match() {
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = cur[u] + 1; i <= n; i++) {
			int v = rk[u][i];
			bool flg = false;
			if (!mat[v]) {
				mat[v] = u;
				flg = true;
			} else if (po[v][mat[v]] > po[v][u]) {
				q.push(mat[v]);
				mat[v] = u;
				flg = true;
			}
			if (flg) { cur[u] = i; break; }
		}
	}
	for (int i = 1; i <= n; i++) ans[mat[i]] = i;
}