题解：CF936B Sleepy Game

· · 题解

题意

原题意较为复杂。注意到走到出度为 0 的点时下一步无法行动，则题意转化为：

给定起点 S，构造一条终点出度为 0 且长度为奇数的路径。

思路

考虑无解的情况。稍微思考一下可以发现，无解时必须满足不存在任意一条长度为奇数的路径且不满足平局的条件。

问题来到如何判断起点到终点是否有长度为奇数的路径。

这个 trick 来源于 P5663 [CSP-J 2019] 加工零件。

维护 dis_{i, 0 / 1} 表示从点 S 出发，长度为偶 / 奇的最短路。

考虑如何转移。对于一条 u \to x 的边而言，用 dis_{u, 0} 松弛 dis_{x, 1}，用 dis_{u, 1} 松弛 dis_{x, 0} 即可。

接下来思考如何平局。平局是好判的，如果我们能在图上转圈圈则可以平局。

形式化地说：如果从起点可以走到一个点数大于 1 的强连通分量中，则可以平局。

这个性质可能会让你往 tarjan 强连通分量缩点的方面上去想，但是题目对于缩点后的图处理较为困难，所以需要使用其他方法代替。

首先 dfs 染色将 S 所有可达的点求出来。接下来可以新建一个只包含染色点的子图，在上面拓扑排序判断是否有环即可。实质上是求染色点和环是否有交。

建子图这一部分是较为重要的，因为拓扑排序中一个环上的点是一定不会入队的，所以这些点指向的点也就不会被遍历到，从而导致一些问题。（WA on #6 #29 #31 #45）

排除上面两种情况，剩下来的就是有解的部分。

题目要求构造路径，则在求最短路时记录前驱即可。

注意在寻找路径时，起点（dis_{S, 1}）也可能被松弛过，因此循环的终止条件是 dis_{pos, now} = 0 而不是 pos = S。（WA on #28）

代码：

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;

const int N = 1e5 + 5;
int n, m, S, T, u, tot, ans[N], deg[N], Deg[N], dis[N][2], pre[N][2];
bool vis[N];
queue<int> q;
vector<int> g[N], G[N];

inline void dfs(int x) {
    vis[x] = true;

    for(auto u : g[x])
        if(! vis[u]) dfs(u);

    return ;
}

inline bool toposort() {
    for(int i = 1 ; i <= n ; ++ i)
        if(vis[i] && Deg[i] == 0) q.push(i);

    while(! q.empty()) {
        int u = q.front();
        q.pop();

        for(auto x : G[u]) {
            -- Deg[x];

            if(Deg[x] == 0) q.push(x);
        }
    }

    for(int i = 1 ; i <= n ; ++ i)
        if(Deg[i] && vis[i]) return true;

    return false;
}

inline void BFS() {
    q.push(S);
    for(int i = 1 ; i <= n ; ++ i)
        dis[i][0] = dis[i][1] = 1e18;
    dis[S][0] = 0;

    while(! q.empty()) {
        int u = q.front();
        q.pop();

        for(auto x : g[u]) {
            if(dis[u][0] + 1 < dis[x][1]) {
                q.push(x);
                pre[x][1] = u;
                dis[x][1] = dis[u][0] + 1;
            }

            if(dis[u][1] + 1 < dis[x][0]) {
                q.push(x);
                pre[x][0] = u;
                dis[x][0] = dis[u][1] + 1;
            }
        }
    }

    return ;
}

signed main() {
    ios_base :: sync_with_stdio(NULL);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++ i) {
        cin >> deg[i];
        for(int j = 1 ; j <= deg[i] ; ++ j) {
            cin >> u;
            g[i].pb(u);
        }
    }
    cin >> S;

    BFS();

    for(int i = 1 ; i <= n ; ++ i) {
        if(deg[i] == 0) {
            if(dis[i][1] != 1e18) {
                T = i;
                goto place;
            }
        }
    }

    dfs(S);

    for(int i = 1 ; i <= n ; ++ i)
        for(auto j : g[i])
            if(vis[i] && vis[j]) {
                ++ Deg[j];
                G[i].pb(j);
            }

    if(toposort()) cout << "Draw";
    else cout << "Lose";

    return 0;

    place:;

    int now = 1;

    cout << "Win\n";
    while(true) {
        ans[++ tot] = T;
        if(dis[T][now] == 0) break ;
        T = pre[T][now];
        now ^= 1;
    }
    for(int i = tot ; i ; -- i)
        cout << ans[i] << ' ';

    return 0;
}

后记