题解：CF2137G Cry Me a River

· · 题解

https://codeforces.com/contest/2137/problem/G

这题是一道明显的 \text{DAG} 加上博弈题，注意一开始我们就要从儿子节点向父亲节点连边，因为题目要求我们采用最优的策略如何到达某个节点，我们就要从后往前面去推。

我们定义 dp_{0/1,i} 表示在当前在节点 i，轮到 Cry/River，当前局面下先手是否有必胜策略。

因为 Cry 获胜的条件是到达一个无出边的节点，所以我们要记录出边度数，用 d_u 表示。

我们使用拓扑排序的思路，对于每一次询问 u，将把 (0,u) 和 (1,u) 加进队列中， 对于每一次更新，如果 (0,v)，则直接加入，但如果是 (1,v) 我们需要考虑是否还有出边，因为题目中要求我们 Cry 获胜条件的限制。

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=200010;
int n,m,Q;
int dp[2][N];
int d[N];
vector<int>V[N];
void solve(){
    int n,m,Q; 
    cin>>n>>m>>Q;
    rep(i,1,n){
        d[i]=dp[0][i]=dp[1][i]=0;
        V[i].clear();
    }
    rep(i,1,m){
        int u,v; cin>>u>>v;
        V[v].push_back(u);
        ++d[u];
    }
    for(;Q;--Q){
        int op,x;
        cin>>op>>x;
        if(op==2) cout<<(dp[1][x]?"NO":"YES")<<'\n';
        else{
            queue<pair<bool,int>>q;
            q.push({1,x}); q.push({0,x});
            for(;!q.empty();){
                bool f=q.front().first;
                int u=q.front().second; q.pop();
                if(dp[f][u]) continue;
                dp[f][u]=1;
                for(auto v:V[u]){
                    if(f==1){
                        q.push({0,v});
                    }else{
                        --d[v];
                        if(d[v]==0){
                            q.push({1,v});
                        }
                    }
                }
            }
        }
    }
}
signed main(){
    int T; cin>>T;
    for(;T;--T) solve();
}