本文主要是介绍poj 1860 拓扑。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考
你有一些古币，现在你要用这些古币去兑换成其他钱币。这个城市里有N个兑换点，每个兑换点包括：
A----钱币AB----钱币B
Rab--A兑换为B的比例
Cab--A兑换为B的手续费
Rba--B兑换为A的比例
Cba--B兑换为A的手续费
现在你有编号为S的这种古币，你将用这些古币去进行一系列的兑换，最终还是要兑换回古币。你想知道能不能通过一系列兑换来增加自身的古币。
N--钱币的种类总数(结点数)
M--兑换点的数量(边的条数)
S--你的货币种类标识(起点&终点)
V--你现在身上货币的数目
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<iomanip>
#include<string>
#include<climits>
#include<cmath>
#define MAXV 110
#define MAXE 110<<1
#define LL long long
using namespace std;
int n,m,start;
float num;
int vis[MAXV];
float money[MAXV];
int cnt[MAXV];
struct Edge
{int to,next;float rate,cost;
};
Edge edge[MAXE];
int index=1;
int first[MAXV];void add(int u,int v,float rate,float cost)
{edge[index].to=v;edge[index].rate=rate;edge[index].cost=cost;edge[index].next=first[u];first[u]=index++;
}
bool spfa()
{memset(cnt,0,sizeof(cnt)),memset(money,0,sizeof(money)),memset(vis,0,sizeof(vis));queue<int>Q;Q.push(start);vis[start]=1;money[start]=num;while(Q.size()){int t=Q.front();Q.pop();vis[t]=0;for(int i=first[t];i;i=edge[i].next){int to=edge[i].to;float tmp=(money[t]-edge[i].cost)*edge[i].rate*1.0;if(money[to]<tmp){money[to]=tmp;if(!vis[to]){Q.push(to);vis[to]=1;}cnt[to]++;if(cnt[to]>n) // 某个结点迭代次数超过了n次，存在正权回路return true;}}}return false;
}int main()
{scanf("%d %d %d %f",&n,&m,&start,&num);int a,b;float r1,c1,r2,c2;memset(first,0,sizeof(first));while(m--){scanf("%d %d %f %f %f %f",&a,&b,&r1,&c1,&r2,&c2);add(a,b,r1,c1);add(b,a,r2,c2);}if(spfa())puts("YES");elseputs("NO");return 0;
}这篇关于poj 1860 拓扑。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
