poj 1860 Currency Exchange （SPFA、正权回路 bellman-ford）

lsyf8

　　链接:poj 1860
　　题意：给定n中货币，以及它们之间的税率，A货币转化为B货币的公式为 B=(V-Cab)*Rab,其中V为A的货币量，
　　求货币S通过若干此转换，再转换为原本的货币时是否会增加
　　分析：这个题就是判断是否存在正权回路，可以用bellman-ford算法，不过松弛条件相反
　　也可以用SPFA算法，判断经过转换后，转换为原本货币的值是否比原值大、、、
　　


　　bellman-ford    0MS


　　#include<stdio.h>
#include<string.h>
struct stu
{
int a,b;
double r,c;
}edge[205];
double v,dis[105];
int s;
int bellmanford(int n,int m)
{
int i,j,flag=0;
memset(dis,0,sizeof(dis));
dis=v;
for(i=1;i<=n-1;i++)
for(j=1;j<=m;j++)
if(dis[edge[j].a]&&(dis[edge[j].a]-edge[j].c)*edge[j].r>dis[edge[j].b])
dis[edge[j].b]=(dis[edge[j].a]-edge[j].c)*edge[j].r;
for(j=1;j<=m;j++)
if(dis[edge[j].a]&&(dis[edge[j].a]-edge[j].c)*edge[j].r>dis[edge[j].b]){
flag=1;
break;
}
return flag;
}
int main()
{
int i,j,l,r,n,m,flag;
while(scanf(&quot;%d%d%d%lf&quot;,&n,&m,&s,&v)!=EOF){
j=1;
for(i=1;i<=m;i++){
scanf(&quot;%d%d&quot;,&l,&r);
scanf(&quot;%lf%lf&quot;,&edge[j].r,&edge[j].c);
edge[j].a=l;
edge[j].b=r;
j++;
edge[j].a=r;
edge[j].b=l;
scanf(&quot;%lf%lf&quot;,&edge[j].r,&edge[j].c);
j++;
}
flag=bellmanford(n,2*m);
if(flag)
printf(&quot;YES\n&quot;);
else
printf(&quot;NO\n&quot;);
}
return 0;
}

SPFA&#43;邻接表  16MS
　　#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct stu
{
int a,b;
double r,c;
}edge[205];
double v,dis[105];
int s,first[205],next[205],vis[105];
int SPFA(int n,int m)
{
int i,pos;
queue<int> q;
memset(dis,0,sizeof(dis));
memset(vis,0,sizeof(vis));
dis=v;
q.push(s);
vis=1;
while(!q.empty()){
pos=q.front();
q.pop();
vis[pos]=0;
i=first[pos];
while(i!=-1){
if((dis[pos]-edge.c)*edge.r>dis[edge.b]){
dis[edge.b]=(dis[pos]-edge.c)*edge.r;
if(!vis[edge.b]){
q.push(edge.b);
vis[edge.b]=1;
}
}
i=next;
}
if(dis>v)
return 1;
}
return 0;
}
int main()
{
int i,j,l,r,n,m,flag;
while(scanf(&quot;%d%d%d%lf&quot;,&n,&m,&s,&v)!=EOF){
j=1;
for(i=1;i<=m;i++){
scanf(&quot;%d%d&quot;,&l,&r);
scanf(&quot;%lf%lf&quot;,&edge[j].r,&edge[j].c);
edge[j].a=l;
edge[j].b=r;
j++;
edge[j].a=r;
edge[j].b=l;
scanf(&quot;%lf%lf&quot;,&edge[j].r,&edge[j].c);
j++;
}
memset(first,-1,sizeof(first));
for(i=1;i<=2*m;i++){
next=first[edge.a];
first[edge.a]=i;
}
flag=SPFA(n,2*m);
if(flag)
printf(&quot;YES\n&quot;);
else
printf(&quot;NO\n&quot;);
}
return 0;
}