Posted on 2008-10-16 15:15
歲月流逝 閱讀(159)
評論(0) 編輯 收藏 引用
題意 ： 一個(gè)famer有一些農(nóng)場，這些農(nóng)場里面有一些田地，田地里面有一些蟲洞，田地和田地之間有路，蟲洞有這樣的性質(zhì)： 時(shí)間倒流。問你這個(gè)農(nóng)民能不能看到他自己，也就是說，有沒有這樣一條路徑，能利用蟲洞的時(shí)間倒流的性質(zhì)，讓這個(gè)人能在這個(gè)點(diǎn)出發(fā)前回去，這樣他就是能看到他自己了
輸入數(shù)據(jù) ：
2 //農(nóng)場個(gè)數(shù)
3 3 1 //田地 路徑 蟲洞 他們的個(gè)數(shù)
1 2 2 //田地路徑 u， v， 以及經(jīng)過需要的時(shí)間
1 3 4
2 3 1
3 1 3 //蟲洞路徑 u， v， 以及倒流的時(shí)間
算法： 首先建有向圖，雙向的路徑也可以表示，然后倒流的時(shí)間設(shè)置為負(fù)權(quán)值。這樣，就判斷這個(gè)圖里面有沒有負(fù)回路就可以了 因?yàn)樨?fù)回路就可以滿足條件，代表總共的需要的時(shí)間是負(fù)的，也就是時(shí)間倒流了。一次bellman。
#include<stdio.h>
#include "memory"
struct node
{
int u;
int v;
int w;
};
node edge[30001];
int eg;
int n,m,w;
bool bellman()
{
int i,j;
int f = 0;
int dist[10000];
memset(dist,0x7f,sizeof(dist));
dist[0]=0;
for(i = 0;i<=n;i++)
{
f = 0;
for(j = 0;j<eg;j++)
{
if(dist[edge[j].v]>dist[edge[j].u]+edge[j].w)
{
dist[edge[j].v]=dist[edge[j].u]+edge[j].w;
f = 1;
}
}
if(!f)
return true;
}
return false;
}
int main()
{
int i;
int cas;
int u,v,val;
scanf("%d",&cas);
while(cas--)
{
eg = 0;
scanf("%d%d%d",&n,&m,&w);
for(i = 0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[eg].u = u;
edge[eg].v = v;
edge[eg].w = val;
eg++;
edge[eg].v = u;
edge[eg].u = v;
edge[eg].w = val;
eg++;
}
for(i = 0;i<w;i++)
{
scanf("%d%d%d",&u,&v,&val);
edge[eg].u = u;
edge[eg].v = v;
edge[eg].w = -val;
eg++;
}
if(bellman())
{
printf("NO\n");
}
else
printf("YES\n");
}
return 0;
}
Tags -
bellman ,
負(fù)環(huán)
文章來源:
http://www.feng5166.com/blog/read.php?126