UVa10557 - XYZZY

题目地址：点击打开链接

解法：

DFS，遍历到某个点，如果该点已被访问并且当前路径能量值大于已保存的该点的能量值，那么存在一个能量值和为正的环，然后判断能否从该点到达终点就可以了。

C++代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxsize = 110; int visited[maxsize]; int n; bool flag; int eneg[maxsize]; int mark[maxsize]; bool flagDfs; struct Room { int energy; int num; vector
     
       vi; }; Room r[maxsize]; void DFS(int i) { if(i==n||flagDfs) { flagDfs=true; return; } mark[i]=1; for(int j=0;j
      
       eneg[k]) { memset(mark,0,sizeof(mark)); flagDfs=false; DFS(i); if(flagDfs) { flag=true; return; } } } } } } } int main() { while(cin>>n&&n!=-1) { int i,j; for(i=1;i<=n;++i) { cin>>r[i].energy>>r[i].num; r[i].vi.clear(); for(j=0;j
       
        >x; r[i].vi.push_back(x); } } memset(eneg,0,sizeof(eneg)); memset(visited,0,sizeof(visited)); flag=false; dfs(1,100); if(flag) cout<<"winnable"<