acd - 1403 - Graph Game（博弈 + 二分圖最大匹配）
來源：程序員人生 發布時間：2014-11-12 09:00:20 閱讀次數：3206次
題意：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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
