学步园

应用bellman_ford算法，求最长路。

相较于标准bellman_ford,写法上，有一点点的改变，即松弛条件变为当没有增值的时候，进行松弛。

但为了防止出现没有增值，也没有点可松弛的时候，记得当没有边松弛的时候，就必须判断并返回。

#include<stdio.h><br /> #include<string.h><br /> #define esp 1e-8<br /> struct node<br /> {<br /> int u,v;<br /> double r,c;<br /> }e[500];<br /> int n,m,s,index;<br /> double source;<br /> double d[200],flag;<br /> double bellman()<br /> {<br /> int i,j,k;<br /> memset(d,0.0,sizeof(d));<br /> d[s]=source;<br /> while(d[s]<=source+esp)<br /> {<br /> flag=1;<br /> for(i=0;i<index;i++)<br /> {<br /> if(d[e[i].v]+esp<(d[e[i].u]-e[i].c)*e[i].r )<br /> {<br /> d[e[i].v]=(d[e[i].u]-e[i].c)*e[i].r;<br /> flag=0;<br /> }<br /> }<br /> if(flag)<br /> {<br /> return d[s]-source;<br /> }<br /> }<br /> return 1;<br /> }<br /> int main()<br /> {<br /> int i,a,b;<br /> double r1,c1,r2,c2;<br /> scanf("%d%d%d%lf",&n,&m,&s,&source);<br /> index=0;<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);<br /> e[index].u=a;e[index].v=b;e[index].r=r1;e[index].c=c1;<br /> e[++index].u=b;e[index].v=a;e[index].r=r2;e[index].c=c2;<br /> index++;<br /> }<br /> if(bellman())<br /> printf("YES/n");<br /> else printf("NO/n");<br /> return 0;<br /> }