題目鏈接在此
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1498。
這個(gè)題是圖的一個(gè)雜題，想不到什么正統(tǒng)的解法，就亂搞了。昨天做了兩個(gè)小時(shí)無果，基本處在搞不清想法的邊緣，然后又不斷的涌出新的想法，好吧。題意是說給定一個(gè)有向圖，每個(gè)點(diǎn)有個(gè)值，要求從點(diǎn)1走到點(diǎn)N，開始走的時(shí)候有初始值。每經(jīng)過一個(gè)點(diǎn)都要加上這個(gè)點(diǎn)的值，問能不能在每一步的值都大于0的情況下走到點(diǎn)N。其實(shí)最先想到的應(yīng)該是點(diǎn)1和點(diǎn)N是連通的。然后就是如何處理環(huán)的問題。我發(fā)現(xiàn)可以在每一個(gè)點(diǎn)記錄以前到達(dá)該點(diǎn)的最大值，如果當(dāng)前走到這個(gè)點(diǎn)的值比最大值小，那么就不需要繼續(xù)走了，因?yàn)樯洗胃蟮臅r(shí)候都走不到，現(xiàn)在值變小了也走不到。大概的想法就是這樣，總結(jié)起來有三點(diǎn)：
1.不走不可聯(lián)通到末尾借點(diǎn)的點(diǎn)。
2.每次走到點(diǎn)的能量應(yīng)該更大。
3.有正環(huán)，并且這個(gè)點(diǎn)可以到達(dá)目的地，則成功。
這個(gè)題糾結(jié)的地方在于DFS判斷圖聯(lián)通會(huì)超時(shí)，我就直接懶的搞寫了個(gè)floyd-wa什么的動(dòng)態(tài)規(guī)劃算法判聯(lián)通性了。
這個(gè)題是個(gè)不落窠臼的題，我首先想到了環(huán)的問題，后來才發(fā)現(xiàn)聯(lián)通問題是更要命的：昨晚寫了個(gè)BFS直接超時(shí)。才發(fā)現(xiàn)這個(gè)題的判聯(lián)通和判能量應(yīng)該分開寫。估計(jì)數(shù)據(jù)有比較惡心的稠密圖，足以讓DFS超時(shí)。而我們可以看到，每個(gè)點(diǎn)就算訪問的最大值不斷增加，也最多有2乘100乘100X100的狀態(tài)（每個(gè)節(jié)點(diǎn)最多訪問2次，節(jié)點(diǎn)的最大值也就是所有可能的總和100X100），所以不會(huì)超時(shí)。而DFS是會(huì)死掉地。
#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;
}