首页 > 代码库 > acd - 1403 - Graph Game(博弈 + 二分图最大匹配)
acd - 1403 - Graph Game(博弈 + 二分图最大匹配)
题意:N与P在玩游戏,N有 n1 个点,P有 n2 个点,N的点与P的点之间有 m 条无向边。将一个石子放在其中一点,N先移动石子,沿边移动一次,石子移动前的点及与该点相连的边被删除,接着到P移动石子,谁不能移动谁就输。对每个初始位置输出胜负结果(1 ≤ n1; n2 ≤ 500, 0 ≤ m ≤ 50 000)。
题目链接:http://acdream.info/problem?pid=1403
——>>二分图的最大匹配可以有很多种,但是,其中可能有些点,无论是哪一种最大匹配方案,都是已盖点。。
那么,先手只要从这样的点沿着匹配边走,就可以把后手逼得走投无路。。(为什么呢?先手从 A 沿着匹配边走到 B,后者从 B 走到另一点 C,假设 C 不是已盖点,则最大匹配的一条匹配边 A - B 可改成 B - C,于是 A 不一定是已盖点,不满足我们的前提条件。。所以,C 一定是已盖点,于是先手可以继续沿着匹配边走,最后把对手干掉)于是,两边各两次dfs找出这样的点即可。。
#include <cstdio> #include <cstring> const int MAXN = 1000 + 10; const int MAXM = 50000 + 10; struct EDGE { int to; int nxt; } edge[MAXM << 1]; int n1, n2, m; int hed[MAXN], ecnt; int S[MAXN], T[MAXN]; bool vis[MAXN]; bool maxMatch[MAXN]; void Init() { ecnt = 0; memset(hed, -1, sizeof(hed)); } void AddEdge(int u, int v) { edge[ecnt].to = v; edge[ecnt].nxt = hed[u]; hed[u] = ecnt++; } void Read() { int u, v; while (m--) { scanf("%d%d", &u, &v); AddEdge(u, v + n1); AddEdge(v + n1, u); } memset(maxMatch, 0, sizeof(maxMatch)); } bool Match(int u) { for (int e = hed[u]; e != -1; e = edge[e].nxt) { int v = edge[e].to; if (!vis[v]) { vis[v] = true; int temps = S[u]; int tempt = T[v]; S[u] = v; T[v] = u; if (tempt == -1 || Match(tempt)) return true; T[v] = tempt; S[u] = temps; } } return false; } bool Judge(int u) { vis[u] = true; if (S[u] == -1) return true; u = S[u]; for (int e = hed[u]; e != -1; e = edge[e].nxt) { int v = edge[e].to; if (!vis[v] && Judge(v)) return true; } return false; } void GetMaxMatchPointLeft() { memset(S, -1, sizeof(S)); memset(T, -1, sizeof(T)); for (int i = 1; i <= n1; ++i) { memset(vis, 0, sizeof(vis)); if (Match(i)) { maxMatch[i] = true; } } for (int i = 1 + n1; i <= n2 + n1; ++i) { if (T[i] != -1) { memset(vis, 0, sizeof(vis)); if (Judge(T[i])) { maxMatch[T[i]] = false; } } } } void GetMaxMatchPointRight() { memset(S, -1, sizeof(S)); memset(T, -1, sizeof(T)); for (int i = 1 + n1; i <= n2 + n1; ++i) { memset(vis, 0, sizeof(vis)); if (Match(i)) { maxMatch[i] = true; } } for (int i = 1; i <= n1; ++i) { if (T[i] != -1) { memset(vis, 0, sizeof(vis)); if (Judge(T[i])) { maxMatch[T[i]] = false; } } } } void Output() { for (int i = 1; i <= n1; ++i) { maxMatch[i] ? putchar('N') : putchar('P'); } puts(""); for (int i = 1 + n1; i <= n2 + n1; ++i) { maxMatch[i] ? putchar('N') : putchar('P'); } puts(""); } int main() { while (scanf("%d%d%d", &n1, &n2, &m) == 3) { Init(); Read(); GetMaxMatchPointLeft(); GetMaxMatchPointRight(); Output(); } return 0; }
acd - 1403 - Graph Game(博弈 + 二分图最大匹配)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。