Posted on 2008-10-16 15:15
岁月流逝 阅读(141)
评论(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