OJ-Problems-Source/HDOJ/1317_autoAC.cpp

100 lines
2.7 KiB
C++
Raw Permalink Normal View History

2016-08-13 23:51:27 +08:00
#include <cstdlib>
#include <iostream>
using namespace std;
const int maxn=102;
struct node
{
int to;
int next;
};
node edge[maxn*maxn];
node edge1[maxn*maxn];
int head[maxn];
int head1[maxn];
bool ac[maxn];
int isin[maxn];
int point[maxn];
int total[maxn];
int stack[maxn+10];
void dfs(int x)
{
isin[x]=1;
ac[x]=true;
for(int k=head1[x];k!=-1;k=edge1[k].next)
{
if(!isin[edge1[k].to])
dfs(edge1[k].to);
}
}
int main()
{
int n,i,j,k,t,x,c,ptr,top;
while(scanf("%d",&n)==1)
{
if(n==-1) break;
if(n==1)
{
printf("winnable\n");
continue;
}
for(i=1;i<=n;i++)
{
head[i]=-1;
head1[i]=-1;
total[i]=-1;
isin[i]=0;
ac[i]=false;
}
c=0;
for(i=1;i<=n;i++)
{
scanf("%d%d",&point[i],&t);
for(j=1;j<=t;j++)
{
scanf("%d",&x);
edge[c].to=x;
edge[c].next=head[i];
head[i]=c;
edge1[c].to=i;
edge1[c].next=head1[x];
head1[x]=c++;
}
}
dfs(n);
if(!ac[1]) printf("hopeless\n");
else
{
for(i=1;i<=n;i++) isin[i]=0;
bool ju=false;
total[1]=100;
ptr=0;
stack[++ptr]=1;
while(ptr&&!ju)
{
top=stack[ptr--];
isin[top]=2;
for(k=head[top];k!=-1&&!ju;k=edge[k].next)
{
if(ac[edge[k].to])
{
int temp=total[top]+point[edge[k].to];
if(temp>0&&temp>total[edge[k].to])
{
total[edge[k].to]=temp;
if(edge[k].to==n||isin[edge[k].to]==2) ju=true;
else if(!isin[edge[k].to])
{
stack[++ptr]=edge[k].to;
isin[edge[k].to]=1;
}
}
}
}
}
if(ju) printf("winnable\n");
else printf("hopeless\n");
}
}
return 0;
}