0%

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

题目

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("");
}
}