UVALive_4318
与一般的在树上进行的选择往哪边走的游戏相比，这个题目不同之处在与每个点既可能成为自己的决策点，也可能成为对方的决策点，因此可以将每个点看成有两种状态，一种对应着博弈树中的max节点，另一种对应着博弈树中的min节点，然后从叶子节点开始向上dp，依次处理出每个节点在两种状态下的值。
#include#include #include #define MAXD 10010#define MAXM 1000010#define INF 0x3f3f3f3fint N, M, F, first[MAXD], e, next[MAXM], v[MAXM], dgr[MAXD], a[MAXD];int S, dp[MAXD][2], vis[MAXD];void add(int x, int y){ v[e] = y; next[e] = first[x], first[x] = e ++; }void init(){ int i, x, y; for(i = 1; i <= N; i ++) scanf("%d", &a[i]); memset(first, -1, sizeof(first[0]) * (N + 1)), e = 0; memset(dgr, 0, sizeof(dgr[0]) * (N + 1)); for(i = 0; i < M; i ++) { scanf("%d%d", &x, &y); add(x, y), ++ dgr[y]; } for(S = 1; dgr[S]; S ++);}void dfs(int cur){ int i; vis[cur] = 1; dp[cur][0] = INF, dp[cur][1] = -INF; for(i = first[cur]; i != -1; i = next[i]) { if(!vis[v[i]]) dfs(v[i]); dp[cur][0] = std::min(dp[cur][0], dp[v[i]][1]); dp[cur][1] = std::max(dp[cur][1], dp[v[i]][0]); } if(dp[cur][0] == INF) dp[cur][0] = dp[cur][1] = 0; dp[cur][0] += a[cur], dp[cur][1] += a[cur];}void solve(){ memset(vis, 0, sizeof(vis[0]) * (N + 1)); dfs(S); printf("%s\n", dp[S][1] >= F ? "Victory" : "Glory");}int main(){ while(scanf("%d%d%d", &N, &M, &F) == 3) { init(); solve(); } return 0;}