首页 > 代码库 > HDU 6105 Gameia（图上博弈）
HDU 6105 Gameia（图上博弈）
题目链接
题意：
有一棵树，所有的节点都是没有涂色的，Alice和Bob依次给没有涂色的节点涂色，Alice涂白色（先手），Bob涂黑色并且会把与这个黑色节点有树边直接相连的节点都涂成黑色（无论这个节点之前是白色还是没有涂色），Bob还有k次机会每次可以删掉一条树边（任何时候都可以执行），直到树上的所有节点都有涂色游戏结束。若树上至少有一个节点是白色Alice获胜，否则Bob获胜。
分析：
Alice先涂一个白色节点，如果Bob想获胜，就必须找到一个未涂色的节点且该节点与白色节点有边相连（相当于每次出现一个白色节点，Bob就必须选一个与白色节点相连的没有涂色的节点涂黑色并把之前白色节点覆盖成黑色，如果Bob不这么做，Alice可以第一次找一个未涂色的叶子节点的直接前驱节点涂白，第二次涂之前白色节点的后继叶子节点就能获胜）。因此Alice一开始找一个叶子节点的直接前驱涂白，则Bob就变成只能把与白色节点直接相连的叶子节点涂黑色（如果Bob涂的是其他节点而不是叶子节点，Alice下次涂叶子节点就能获胜）。每进行一轮就把已经涂色的点遮掉（一对是黑色，一个匹配）剩下的就又是若干棵所有节点都未涂色的树（可能是孤立的节点），再执行上次的操作。问题就变成每两个有直接边相连的一对节点组成一个匹配，所有节点是否都在某一个匹配中。显然奇数个节点一定无法满足前面那个条件，Alice获胜；偶数个节点若不能满足之前那个匹配条件，在某次遮掉一个匹配时会产生孤立节点，也是Alice获胜；如果偶数节点存在两两匹配的情况，而Bob的删边次数不足以把树分成两两的点对，Alice一定获胜，因为树分成两两匹配的点对，其中Alice可以迫使Bob把一个点对中的一个点P涂黑（假设点P与另个匹配A中的点Q相连，则匹配A中的Q被涂黑，匹配A的另一个点就失去匹配，最后会出现一个孤立点。
程序实现：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
const int N = 500 + 5;
vector<int> G[N];
bool mark, vis[N];
void dfs(int x, int fa)
{
for (int i = 0; i < G[x].size(); i++)
dfs(G[x][i], x);
if (vis[x]) return;//当前节点已经匹配了
else {
if (vis[fa]) mark = 0;//当前节点没有匹配，其父节点匹配了，原树就不能两两匹配
else vis[x] = vis[fa] = 1;//当前节点与其父节点匹配
}
return ;
}
int main()
{
int T, n, k, fa;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) G[i].clear();
for (int i = 2; i <= n; i++) {
scanf("%d", &fa);
G[fa].push_back(i);
}
if (n % 2) {
puts("Alice");
continue;
}
memset(vis, 0, sizeof(vis));
mark = 1;//标记是否两两匹配
dfs(1, 1);
if (mark && n-1 - n/2 <= k) puts("Bob");
else puts("Alice");
}
return 0;
}
HDU 6105 Gameia（图上博弈）