题解：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 获胜条件的限制。

CPP

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

题解：CF2137G Cry Me a River

文章操作

相关推荐

评论

题解：CF2137G Cry Me a River