Posted on 2008-10-16 15:15
歲月流逝 閱讀(144)
評論(0) 編輯 收藏 引用
題意 ： 一個famer有一些農場，這些農場里面有一些田地，田地里面有一些蟲洞，田地和田地之間有路，蟲洞有這樣的性質： 時間倒流。問你這個農民能不能看到他自己，也就是說，有沒有這樣一條路徑，能利用蟲洞的時間倒流的性質，讓這個人能在這個點出發前回去，這樣他就是能看到他自己了
輸入數據 ：
2 //農場個數
3 3 1 //田地 路徑 蟲洞 他們的個數
1 2 2 //田地路徑 u， v， 以及經過需要的時間
1 3 4
2 3 1
3 1 3 //蟲洞路徑 u， v， 以及倒流的時間
算法： 首先建有向圖，雙向的路徑也可以表示，然后倒流的時間設置為負權值。這樣，就判斷這個圖里面有沒有負回路就可以了 因為負回路就可以滿足條件，代表總共的需要的時間是負的，也就是時間倒流了。一次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 ,
負環
文章來源:
http://www.feng5166.com/blog/read.php?126