acd - 1403 - Graph Game（博弈 + 二分图最大匹配）
来源：程序员人生 发布时间：2014-11-12 09:00:20 阅读次数：3063次
题意：N与P在玩游戏，N有 n1 个点，P有 n2 个点，N的点与P的点之间有 m 条无向边。将1个石子放在其中1点，N先移动石子，沿边移动1次，石子移动前的点及与该点相连的边被删除，接着到P移动石子，谁不能移动谁就输。对每一个初始位置输出胜负结果(1 ≤ n1; n2 ≤ 500, 0 ≤ m ≤ 50 000)。
题目链接：http://acdream.info/problem?pid=1403
――>>2分图的最大匹配可以有很多种，但是，其中可能有些点，不管是哪种最大匹配方案，都是已盖点。。
那末，先手只要从这样的点沿着匹配边走，就能够把后手逼得走投无路。。（为何呢？先手从 A 沿着匹配边走到 B，后者从 B 走到另外一点 C，假定 C 不是已盖点，则最大匹配的1条匹配边 A - B 可改成 B - C，因而 A 不1定是已盖点，不满足我们的条件条件。。所以，C 1定是已盖点，因而先手可以继续沿着匹配边走，最后把对手干掉）
因而，两边各两次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, ⑴, 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 != ⑴; 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 == ⑴ || Match(tempt)) return true;
T[v] = tempt;
S[u] = temps;
}
}
return false;
}
bool Judge(int u)
{
vis[u] = true;
if (S[u] == ⑴) return true;
u = S[u];
for (int e = hed[u]; e != ⑴; e = edge[e].nxt)
{
int v = edge[e].to;
if (!vis[v] && Judge(v)) return true;
}
return false;
}
void GetMaxMatchPointLeft()
{
memset(S, ⑴, sizeof(S));
memset(T, ⑴, 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] != ⑴)
{
memset(vis, 0, sizeof(vis));
if (Judge(T[i]))
{
maxMatch[T[i]] = false;
}
}
}
}
void GetMaxMatchPointRight()
{
memset(S, ⑴, sizeof(S));
memset(T, ⑴, 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] != ⑴)
{
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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
