Problem
Source: BSOJ 3077
Description
话说前年 Alice 和 Bob 相聚在一起玩游戏后,彼此都很忙,因此很少见面。今年由于为了 NOIP2011 又再次相聚,他们俩还是想比比谁能够收集到最多的石子数量。Alice 将石子分成了 N 堆(编号 $1 \dots N$),并且规定了它们的选取顺序,刚好形成一颗有向树。在游戏过程中,两人从根节点开始,轮流取走石子,当一个人取走节点 $i$ 的石子后,另一个人只能从节点 $i$ 的儿子节点中选取一个。当取到某个叶子时游戏结束,然后两人会比较自己得到的石子数量。已知两人采用的策略不一样,Alice 考虑在让 Bob 取得尽可能少的前提下,自己取的最多;而 Bob 想得是在自己尽可能取得多的前提下,让 Alice 取得最少。在两人都采取最优策略的情况下,请你计算出游戏结束时两人的石子数量。
游戏总是 Alice 先取,保证只存在一组解。
数据范围:
-
对于 $30\%$ 的数据,$1\leq N \leq 100$,$1 \leq \text{num}[i] \leq 100$
-
对于 $60\%$ 的数据,$1\leq N\leq 10,000$,$1\leq \text{num}[i]\leq 10,000$
-
对于 $100\%$ 的数据,$1\leq N\leq 100,000$,$1\leq \text{num}[i]\leq 10,000$
Input
第 1 行只有一个正整数 $N$,表示石子堆数;
第 2 行包含 $N$ 个整数,第 $i$ 个数表示第 $i$ 堆石子的数量 $\text{num}[i]$;
第 $3 \dots N+1$ 行,每行两个正整数 $u$ 和 $v$,表示节点 $u$ 为节点 $v$ 的父亲;
Output
输出文件仅一行为两个整数,分别表示 Alice 取到的石子数和 Bob 取到的石子数。
Sample Input
6
4 16 16 5 3 1
1 2
2 4
1 3
3 5
3 6
Sample Output
7 16
Output Details
首先 Alice 一定能取得节点 1 的 4 个石子,留给 Bob 的是节点 2 和 3,均为 16 个石子。若选取节点 2 则 Alice 下一次可以最多得到 5 个石子,而选择 3,则 Alice 最多也只能得到 3 个石子,所以此时 Bob 会选择节点 3,故 Alice 最后得到的石子数为 7,Bob 为 16。
Solution
首先应该对每个点进行染色,根据该点到根的距离,判断出该点是先手取到还是后手取到。然后对该点进行记忆化搜索,根据先后手情况有下面两个计算公式:
$f[i][2]$ 中 $f[i][0]$:节点 $i$ 为子树的博弈中先手能够取到的得分
$f[i][1]$:节点 $i$ 为子树的博弈中后手能够取到的得分
-
若节点 $i$ 为 Alice 取得:
for j ∈ i.child if(f[j][0] > f[i][1] || (f[j][0] == f[i][1] && f[j][1] < f[i][0])) { f[i][0] ← f[j][1]; f[i][1] ← f[j][0]; } f[i][0] ← f[i][0] + value[i]
-
若节点 $i$ 为 Bob 取得:
for j ∈ i.child if(f[j][1] < f[i][0] || (f[j][1] == f[i][0] && f[j][0] > f[i][1])) { f[i][0] ← f[j][1]; f[i][1] ← f[j][0]; } f[i][0] ← f[i][0] + value[i]
最后输出根节点的 $f[root][0]$ 和 $f[root][1]$ 即为答案。
由于数据范围较大,直接 DFS 会爆栈,所以需要使用人工栈,或是从叶节点进行 BFS 反推至根节点。
Code
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int M = 1000005, inf = 0x7fffffff/2;
struct node {
int to, next;
} T[M];
int a[M], h[M], vis[M], color[M], ch[M], f[M][2], father[M], q[M];
int cnt, root, n;
void AddEdge(int x, int y) {
cnt++;
T[cnt].to = y;
T[cnt].next = h[x];
h[x] = cnt;
}
void Dye() {
int L = 0, R = 1;
q[R] = root;
while(L != R) {
L = (L+1) % M;
int k = q[L];
for(int i = h[k]; i; i = T[i].next) {
int to = T[i].to;
if(!color[to]) {
color[to] = 3 - color[k];
R = (R + 1) % M;
q[R] = to;
}
}
}
}
void Bfs() {
int L = 0, R = 0;
for(int i = 1; i <= n; i++) {
f[i][0] = inf, f[i][1] = 0;
if(ch[i] == 0) q[++R] = i, f[i][0] = 0;
}
while(L != R) {
L = (L + 1) % M;
int v = q[L], u = father[v];
f[v][0] += a[v];
if(color[v] == 1) {
if(f[v][1] < f[u][0] || (f[v][1] == f[u][0] && f[v][0] > f[u][1]))
f[u][0] = f[v][1], f[u][1] = f[v][0];
}
else {
if(f[v][0] > f[u][1] || (f[v][0] == f[u][1] && f[v][1] < f[u][0]))
f[u][0] = f[v][1], f[u][1] = f[v][0];
}
if(!--ch[u]) {
R = (R + 1) % M;
q[R] = u;
}
}
}
int main() {
int u, v;
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i < n; i++) {
scanf("%d%d", &u, &v);
AddEdge(u, v);
vis[v] = 1, ch[u]++, father[v] = u;
}
for(int i = 1; i <= n; i++)
if(!vis[i]) {
root = i;
break;
}
color[root] = 1;
Dye();
Bfs();
printf("%d %d\n", f[root][0], f[root][1]);
return 0;
}