poj 1860

我们熟悉的算法dijkstra可用于求单源点到其他各点的最短距离。但是有一个问题在于，图中所有边的权之都应该为正值。因为如果有负权值的边，则只要绕着这条负值边一直走，最算路径很可能越来越短。而这正是bellman ford算法的思想：如果路径可以缩短，那么就按照dijkstra的算法让路径进行N-1次（N为图中的顶点个数）缩短。如果N-1次缩短之后仍能继续缩短，那么图中必定存在负边。

算法的思想参见维基百科里关于bellman Ford算法的解释：

bellman ford算法

把每个货币币种看作图的一个顶点，把兑换过程看作顶点之间的动态的有向边（注意，是动态的有向边，因为货币数量与兑换完的数量之间是一个函数关系，而不是固定的）。那么：

poj1860这道题，则刚好把“缩短”这个概念换为“货币能增值”，如果经过某个环，让货币增值了，那么就可以让主人公的货币一直增长下去。进行N-1次“增值”之后，如果还能继续增值，则说明图中存在能无限把货币增值的环。

poj1860代码：

#include<iostream>
#include<fstream>

using namespace std;
int N,M,S;
int all;
double V;
double dis[202];
struct Edge
{
   int v1;
   int v2;
   double rat;
   double com;
}edges[404];
bool bellmanford()
{
	for(int i=0;i<N-1;i++)
	{
            bool flag=false;
	    for(int j=0;j<all;j++)
	    {
		    int v1=edges[j].v1;
		    int v2=edges[j].v2;
		    if((dis[v1]-edges[j].com)*edges[j].rat>dis[v2])
		    {
			    dis[v2]=(dis[v1]-edges[j].com)*edges[j].rat;
			    flag=true;
		    }
	    }
	    if(flag==false)
		    break;
	}
	for(int j=0;j<all;j++)
	{
		int v1=edges[j].v1;
		int v2=edges[j].v2;
		if((dis[v1]-edges[j].com)*edges[j].rat>dis[v2])
			return true;
	}
	return false;
}
int main()
{

	 
	while(cin>>N>>M>>S>>V)
	{
		all=0;
		for(int i=0;i<M;i++)
		{
                   cin>>edges[all].v1>>edges[all].v2>>edges[all].rat>>edges[all].com;
		   edges[all+1].v1=edges[all].v2;
		   edges[all+1].v2=edges[all].v1;
		   all++;
		   cin>>edges[all].rat>>edges[all].com;
		   all++;
		}
		for(int i=1;i<=N;i++)
		{
			dis[i]=0;
		}
		dis[S]=V;
		if(bellmanford())
		{
			cout<<"YES"<<endl;
		}
		else 
			cout<<"NO"<<endl;
	}
	return 0;
}