题目链接在此
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1498。
这个题是图的一个杂题，想不到什么正统的解法，就乱搞了。昨天做了两个小时无果，基本处在搞不清想法的边缘，然后又不断的涌出新的想法，好吧。题意是说给定一个有向图，每个点有个值，要求从点1走到点N，开始走的时候有初始值。每经过一个点都要加上这个点的值，问能不能在每一步的值都大于0的情况下走到点N。其实最先想到的应该是点1和点N是连通的。然后就是如何处理环的问题。我发现可以在每一个点记录以前到达该点的最大值，如果当前走到这个点的值比最大值小，那么就不需要继续走了，因为上次更大的时候都走不到，现在值变小了也走不到。大概的想法就是这样，总结起来有三点：
1.不走不可联通到末尾借点的点。
2.每次走到点的能量应该更大。
3.有正环，并且这个点可以到达目的地，则成功。
这个题纠结的地方在于DFS判断图联通会超时，我就直接懒的搞写了个floyd-wa什么的动态规划算法判联通性了。
这个题是个不落窠臼的题，我首先想到了环的问题，后来才发现联通问题是更要命的：昨晚写了个BFS直接超时。才发现这个题的判联通和判能量应该分开写。估计数据有比较恶心的稠密图，足以让DFS超时。而我们可以看到，每个点就算访问的最大值不断增加，也最多有2乘100乘100X100的状态（每个节点最多访问2次，节点的最大值也就是所有可能的总和100X100），所以不会超时。而DFS是会死掉地。
#include <cstdio>#include <cstring>
int nmap[110][110];
int lstv[110];
int vistime[110];
int reach[110][110];
int eng[110];
int N;
int nfind;
void dfs(int n,int value)
{
if(nfind == 1) return;
if(n == N && value > 0)
{
nfind = 1;
return;
}
int i;
for(i=1;i<=N;i++)
{
if(reach[i][N] && nmap[n][i] && lstv[i] < value+eng[i] && value+eng[i] > 0)
{
vistime[i]++;
if(vistime[i] >= 2)
{
nfind = 1;
return;
}
lstv[i] = value + eng[i];
dfs(i,lstv[i]);
vistime[i]--;
}
}
}
int main()
{
int a,b,c,tmp,i,j,k;
while(scanf("%d",&N) && N != -1)
{
memset(nmap,0,sizeof(nmap));
memset(reach,0,sizeof(reach));
for(i=1;i<=N;i++)
{
scanf("%d",&eng[i]);
scanf("%d",&tmp);
for(j=0;j<tmp;j++)
{
scanf("%d",&b);
nmap[i][b] = reach[i][b] = 1;
}
}
for(i=1;i<=N;i++)
lstv[i] = -1000000;
for(k=1;k<=N;k++)
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
if(reach[i][k]>0 && reach[k][j]>0)
reach[i][j] = 1;
}
reach[N][N] = 1;
memset(vistime,0,sizeof(vistime));
vistime[1]++;
nfind = 0;
if(reach[1][N])
dfs(1,100);
/* for(i=1;i<=N;i++)
{
for(j=1;j<=N;j++)
printf("%d ",reach[i][j]);
printf("\n");
}*/
if(nfind) printf("winnable\n"); else printf("hopeless\n");
}
return 0;
}