#include<stdio.h>
const int MAX=105;
const double EXP=1e-8;
double dis[MAX];
struct Edge
{
int v1,v2;
double c,r;
};
Edge edge[MAX*2];
int m,n,s;
double v;
bool bellman_ford()
{
for(int i=1;i<=n;i++) dis[i]=0;
dis[s]=v;
while(dis[s]<=v)
{
bool relax=0;
for(int i=0;i<m;i++)
if(dis[edge[i].v2]<(dis[edge[i].v1]-edge[i].c)*edge[i].r)
{
relax=1;
dis[edge[i].v2]=(dis[edge[i].v1]-edge[i].c)*edge[i].r;
}
if(!relax) return false;
}
return true;
}
int main()
{
while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF)
{
for(int i=0;i<m;i++)
{
scanf("%d%d%lf%lf%lf%lf",&edge[i*2].v1,&edge[i*2].v2,&edge[i*2].r,&edge[i*2].c,&edge[i*2+1].r,&edge[i*2+1].c);
edge[i*2+1].v1=edge[i*2].v2;edge[i*2+1].v2=edge[i*2].v1;
}
m*=2;
if(bellman_ford()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
|
总结:
可以在两点间循环往复兑换从而可以使钱不断增加,也就是图中存在局部回路,可以采用Bellman-Fold算法进行松弛,逐步增大源点s到点v的最短路的估算值。
阅读(609) | 评论(0) | 转发(0) |