Currency Exchange（货币交换）
poj 1860题目大意：给出n货币种类数，从1....n,给出m表示交换货币的地点，s表示源点的编号，v表示起始总钱数，接下来m行，每行6个分别是从a到b和a到b的利率，a到b的费用，b到a的利率，b到a的费用，可以建图了。
解决：spfa直接就出来了
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int v;
double w,c;
int next;
};
node e;
const int N=110;
int pos;
int head;
int n,m,s;
double tot;
double dist;
bool inq;
int cnt;
void init()
{
for(int i=1;i<=n;i++)
{
dist=-0x2f2f2f2f;//初始化dist最小
cnt=0;
inq=0;
head=-1;
}
}
void addedge(int u,int v,double w,double c)
{
e.v=v;
e.w=w;
e.c=c;
e.next=head;
head=pos++;
}
void spfa()
{
queue<int> q;
int v0=s;
q.push(v0);
dist=tot;//初始化源点的dist值即最开始手中的钱
inq=1;
int v; //就是一spfa算法
double w,c;
while(!q.empty())
{
v0=q.front();
q.pop();
inq=0;
for(int i=head;i!=-1;i=e.next)
{
v=e.v;
w=e.w;
c=e.c;
if((dist-c)* w > dist)
{
dist=(dist-c)* w;
//判断源点的钱是不是增加了，增加就退出了
if(dist>tot){puts("YES");return;}
if(!inq)
{
inq=1;
q.push(v);
}
}
}
}
//结束还没退出就不行了
puts("NO");
}
int main()
{
scanf("%d%d%d%lf",&n,&m,&s,&tot);
pos=0;
init();
int a,b;
double r1,c1,r2,c2;
getchar();
for(int i=0;i<m;i++)
{
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
addedge(a,b,r1,c1);
addedge(b,a,r2,c2);
}
spfa();
system("pause");
return 0;
}
There can be several points specializing in the same pair of currencies. Each
point has its own exchange rates,这句话说明了有重复的边，我干脆用了邻接矩阵，因为之前花费一天时间a了第一道查分约束，用到了邻接矩阵建图，所以这题一次就过了，听顺的，呵呵，再次说明不会的题，实在想不起来了先放放，做其他题找灵感，
页:
[1]