題目鏈接在此
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;
}