poj 1860 拓扑。。

参考

你有一些古币，现在你要用这些古币去兑换成其他钱币。这个城市里有N个兑换点，每个兑换点包括：

A----钱币A
B----钱币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; }hdu上待做：  We have carefully selected several similar problems for you:   2647   3333   3339   3341   3336  

总结

以上是生活随笔为你收集整理的poj 1860 拓扑。。的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。