感觉最短路好神奇呀,刚开始我都 没想到用最短路
题目:http://poj.org/problem?id=1860
题意:有多种从a到b的汇率,在你汇钱的过程中还需要支付手续费,那么你所得的钱是 money=(nowmoney-手续费)*rate,现在问你有v钱,从s开始出发交换钱能不能赚钱
题解:这题其实是用bellman_ford的思想,通过n-1次松弛后,如果还能增加,就说明有环 可以使金钱数不断增加。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
int cnt;
double dis[];
double n,m,v;
struct node
{
int u,v,next;
double r,c;
}edge[]; void add(int u,int v,double r,double c)
{
edge[cnt].u=u; edge[cnt].v=v;
edge[cnt].r=r; edge[cnt++].c=c;
}
int bellman_ford(int s)
{
int i,j;
for(i=; i<n; i++)
dis[i]=;
dis[s]=v; //跟最短路不一样,到自己的距离是原来的钱数
for(i=; i<n-; i++)
for(j=; j<cnt; j++)
{
if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//逆用最短路
dis[edge[j].v]=(dis[edge[j].u]-edge[j].c)*edge[j].r;
}
for(j=; j<cnt; j++)
if(dis[edge[j].v]<(dis[edge[j].u]-edge[j].c)*edge[j].r)//如果成立说明有能使钱数增加的环
return ;
return ;
}
int main()
{
int s,i,j,a,b;
double rab,cab,rba,cba;
scanf("%lf%lf%d%lf",&n,&m,&s,&v);
cnt=;
for(i=; i<m; i++)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
add(a,b,rab,cab);
add(b,a,rba,cba);
}
if(bellman_ford(s)) printf("YES\n");
else printf("NO\n");
return ;
}
这个博客:http://blog.****.net/wangjian8006/article/details/7871753
就是到s的距离大于v了,就是YES。
有spfa的代码,这个应该理论上更省时间