POJ 1860 Currency Exchange（最短路&spfa正权回路）题解
发布时间
阅读量：
阅读量
题意：存在n类货币以及m种汇率转换方式。对于ab两种货币间的汇率为p（即1ab= p cd），手续费为q，则兑换后得到的cd货币数量b= (a - q) * p。假设你的第s类货币存有数量为v，请问能否通过货币转化使你的第s类货币数量增加？
在处理过程中可能出现负权值的情况下，则考虑采用spfa算法来处理问题。具体来说就是需要判断是否存在正权回路，并考察此时变量dis[s]是否被进一步增大。为此我们需要将变量dis初始化为0，在后续的过程中进行相应的转换操作。每次循环都会检查一次当前变量s对应的dis[s]值是否能够进一步增大并据此进行更新操作。
参考文献：最快速度和高可用性的spfa算法
代码：
#include<cstdio>
#include<set>
#include<vector>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn = 100+5;
const int INF = 0x3f3f3f3f;
struct Edge{
int v;
double cost,dec;
Edge(int _v = 0,double _c = 0,double _d = 0):v(_v),cost(_c),dec(_d){}
};
vector<Edge> G[maxn];
bool vis[maxn]; //在队列标志
//int cnt[maxn]; //每个点入队列次数
double dis[maxn];
bool spfa(int start,double V,int n){
memset(vis,false,sizeof(vis));
for(int i = 1;i <= n;i++) dis[i] = 0;
vis[start] = true;
dis[start] = V;
queue<int> q;
while(!q.empty()) q.pop();
q.push(start);
//memset(cnt,0,sizeof(cnt));
//cnt[start] = 1;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i = 0;i < G[u].size();i++){
int v = G[u][i].v;
double c = G[u][i].cost;
double d = G[u][i].dec;
if(dis[v] < (dis[u] - d)*c){
dis[v] = (dis[u] - d)*c;
if(!vis[v]){
q.push(v);
vis[v] = true;
/*if(++cnt[v] > n)
return false;*/
}
}
if(dis[start] > V)
return true;
}
}
return false;
}
void addEdge(int u,int v,double cost,double dec){
G[u].push_back(Edge(v,cost,dec));
}
int main(){
int n,m,s;
double V;
while(scanf("%d%d%d%lf",&n,&m,&s,&V) != EOF){
for(int i = 1;i <= n;i++) G[i].clear();
for(int i = 0;i < m;i++){
int u,v;
double c,d;
scanf("%d%d%lf%lf",&u,&v,&c,&d);
addEdge(u,v,c,d);
scanf("%lf%lf",&c,&d);
addEdge(v,u,c,d);
}
bool flag = spfa(s,V,n);
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}全部评论 (0)
还没有任何评论哟~