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;jeneg[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"<