代码如下,过了测试数据。
记忆化dp
注意visit[a][b][tag]记录是否之前到达了当前的状态,如果到达过,说明进入了一个环,回溯。
注意回溯的时候,不要设置res[a][b][tag],因为该结果可能尚未产生。
#include<vector> #include<iostream> #include<string.h> using namespace std; // -1: alice win, 1: bob win, -2: inited int res[100][100][2];//[a][b][if a go now] bool visit[100][100][2]; // -1: alice win, 1: bob win // a_f: if alice go now int dfs(vector<vector<int> > &tree,int a, int b, bool a_f){ // cout<<a<<":"<<b<<":"<<a_f<<endl; if(res[a][b][a_f]!=-2) return res[a][b][a_f]; if(a==b) return res[a][b][a_f]=-1; if(visit[a][b][a_f]) return 1; //回溯(res[a][b][a_f]结果未必产生) visit[a][b][a_f] = true; int t=-3; if(a_f){//a go for(int i=0; i<tree[a].size(); i++){ int a1=tree[a][i]; t=dfs(tree, a1, b, false); if(t==-1) break; } // if t==-3 or 1, then bob win res[a][b][a_f]=t==-3?1:t; }else{ for(int i=0; i<tree[b].size(); i++){ int b1=tree[b][i]; t=dfs(tree, a, b1, true); if(t!=-1) break; } // if t==-3 or -1, then alice win res[a][b][a_f]=t==-3?-1:t; } visit[a][b][a_f]=false; return res[a][b][a_f]; } int main(){ int cases; cin>>cases; for(int casei=1; casei<=cases; casei++){ int n, m; cin>>n>>m; vector<vector<int> > tree(n, vector<int>()); for(int i=0; i<m; i++){ int a, b; cin>>a>>b; a--, b--; tree[a].push_back(b); } memset(visit, 0, sizeof(visit)); for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ for(int k=0; k<2; k++){ res[i][j][k]=-2; } } } int a, b; cin>>b>>a; a--, b--; int s=dfs(tree, a, b, false); cout<<"Case #"<<casei<<": "; if(s==1) cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }