POJ1860（Currency Exchange）

POJ1860（Currency Exchange）

题意：

    给出一张各种货币交换的网络，问在网络中交换原有的货币，问货币能否增值?

解析：

判断是否存在正环即可  用spfa  负环和正环的判定方法一样  如果一个点的进队次数超过n次 则存在环

 

代码如下：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 10010, INF = 0xfffffff;
struct node{int u,v,next;double rat,cost;
}Node[maxn];
int n,m,mon;
double num;
int cnt[maxn],vis[maxn],head[maxn];
double d[maxn];
void add(int u,int v,double rat,double cost,int i)
{Node[i].u = u;Node[i].v = v;Node[i].rat = rat;Node[i].cost = cost;Node[i].next = head[u];head[u] = i;}int spfa(int s)
{queue<int> Q;mem(d,0);mem(vis,0);d[s] = num;Q.push(s);vis[s] = 1;while(!Q.empty()){int x = Q.front();Q.pop();vis[x] = 0;for(int i=head[x]; i!=-1; i=Node[i].next){node e = Node[i];if(d[e.v] < (d[x]-e.cost)*e.rat){d[e.v] = (d[x]-e.cost)*e.rat;if(!vis[e.v]){Q.push(e.v);vis[e.v] = 1;if(++cnt[e.v] > n) return 1;   //判断是否进队n次}}}}return 0;     //千万别忘了写这个  wa了n次}int main()
{while(cin>>n>>m>>mon>>num){mem(Node,0);mem(cnt,0);mem(head,-1);int ans = 0;for(int i=0; i<m; ++i){int u,v;double urat,ucost,vrat,vcost;cin>>u>>v>>urat>>ucost>>vrat>>vcost;add(u,v,urat,ucost,ans++);add(v,u,vrat,vcost,ans++);}if(spfa(mon))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}return 0;
}

 

转载于:.html