【题解】BZOJ-4845-[Neerc2016]Game on Graph

Posted on In Disqus:

题目

http://codeforces.com/gym/101190/problem/G

题意

给一个有向图，在某个顶点上有一颗棋子，双方轮流移动棋子，当棋子无法移动时判负。对 Alice 来说，平>赢>输，对 Bob 来说，赢>输>平。求对于棋子的所有初始位置和先后手，最终的胜负情况。

题解

  • Alice 优先平，Bob 优先赢。当两者都无法得到最优结果会导致，Alice 赢（一个愿打，一个愿挨）。
  • 考虑 Alice 不能平的状态，显然终止态都不能平。其他状态，如果 Alice 先，不能平当且仅当后继状态都不能平，如果 Bob 先，不能平当且仅当后继状态中存在不能平的。
  • 对于 Bob 能赢的状态也是类似考虑。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int maxn = 1E5 + 100;
vector<int> rG[maxn];
int out[maxn], tout[maxn];
bool draw[maxn][2], win[maxn][2];

int main() {
#ifndef zerol
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
#endif
    int n, m; cin >> n >> m;
    FOR (_, 0, m) {
        int u, v; scanf("%d%d", &u, &v);
        rG[v].push_back(u); tout[u]++;
    }

    // 0 (to draw) 1 (to win)
    // force draw
    FOR (i, 1, n + 1) {
        draw[i][0] = draw[i][1] = true;
        out[i] = tout[i];
    }
    queue<pair<int, int>> q;
    FOR (i, 1, n + 1)
        if (!out[i]) {
            q.push({i, 0}); q.push({i, 1});
        }
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int u = p.first, t = p.second;
        if (!draw[u][t]) continue;
        draw[u][t] = false;
        for (int& v: rG[u]) {
            if (t == 0) q.push({v, 1});
            else if (--out[v] == 0) q.push({v, 0});
        }
    }

    // force win
    FOR (i, 1, n + 1) {
        win[i][0] = win[i][1] = false;
        out[i] = tout[i];
    }
    FOR (i, 1, n + 1)
        if (!out[i]) {
            q.push({i, 0});
        }
    while (!q.empty()) {
        auto p = q.front(); q.pop();
        int u = p.first, t = p.second;
        if (win[u][t]) continue;
        win[u][t] = true;
        for (int& v: rG[u]) {
            if (t == 0) q.push({v, 1});
            else if (--out[v] == 0) q.push({v, 0});
        }
    }

    // output
    FOR (t, 0, 2) {
        FOR (i, 1, n + 1)
            if (draw[i][t]) putchar('D');
            else putchar(win[i][t] ^ t == 1 ? 'L' : 'W');
        puts("");
    }
}