poj1860 最短路 无限增大环

Description

Input

Output

Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

Sample Output

YES

Source

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define INF 10000000.0

using namespace std;

struct node
{
    int u,v;
    double r;
    double c;
} edge[10000];
int n,m,s;
double v;
double low[10000];
int a,b;
double rab,cab,rba,cba;
int num=0;
int Bellman(int u0)
{
    for(int i=0; i<=n; i++)
        low[i]=0;
    low[u0]=v;
    for(int i=0; i<n-1; i++)
    {
        int flag=0;
        for(int j=0; j<num; j++)
        {
            if((low[edge[j].u]-edge[j].c)*edge[j].r>low[edge[j].v]+(1e-10))
            {
                low[edge[j].v]=(low[edge[j].u]-edge[j].c)*edge[j].r;
                flag=1;
            }
        }
        if (flag==0)
            break;
    }

    for(int j=0; j<num; j++)//判断有无无限增加环   ,类似判负权回路
    {
        if((low[edge[j].u]-edge[j].c)*edge[j].r>low[edge[j].v]+(1e-10))
            return 1;
    }
    return 0;
}
int main()
{
    while(~scanf("%d%d%d%lf",&n,&m,&s,&v))//定义了double不可用%f读入
    {
        num=0;
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
            edge[num].u=a;
            edge[num].v=b;
            edge[num].r=rab;
            edge[num++].c=cab;
            edge[num].u=b;
            edge[num].v=a;
            edge[num].r=rba;
            edge[num++].c=cba;
        }
        if(Bellman(s))
            printf("YES\n");
        else
            printf("NO\n");
    }
}

  /*int Bellman(int u0)
{
	for(int i=0;i<=n;i++)
	low[i]=0;
	low[u0]=v;
	while(low[u0]<=v+(1e-10))     //此处的兑换可以无限进行,所以就不是递推 n 了;
	{                                                          <span id="transmark"></span>//可以存在可以无限增大的环
		int flag=0;                               
		for(int j=0;j<num;j++)
		{
			if((low[edge[j].u]-edge[j].c)*edge[j].r>low[edge[j].v]+(1e-10))
			{
				low[edge[j].v]=(low[edge[j].u]-edge[j].c)*edge[j].r;
				flag=1;
			}
		}
		if (flag==0)
			break;
	}
	if(low[u0]>v)
		return 1;
	return 0;
}*/

poj1860 最短路 无限增大环

原文：http://blog.csdn.net/became_a_wolf/article/details/47781855