本文共 1554 字，大约阅读时间需要 5 分钟。
你有一些古币，现在你要用这些古币去兑换成其他钱币。这个城市里有N个兑换点，每个兑换点包括：
A----钱币A B----钱币B Rab--A兑换为B的比例 Cab--A兑换为B的手续费 Rba--B兑换为A的比例 Cba--B兑换为A的手续费 现在你有编号为S的这种古币，你将用这些古币去进行一系列的兑换，最终还是要兑换回古币。你想知道能不能通过一系列兑换来增加自身的古币。 N--钱币的种类总数(结点数) M--兑换点的数量(边的条数) S--你的货币种类标识(起点&终点) V--你现在身上货币的数目 #include #include #include #include #include #include #include #include #include #include #include #include #define MAXV 110#define MAXE 110<<1#define LL long longusing 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 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] 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"); else puts("NO"); return 0;}
hdu上待做：
We have carefully selected several similar problems for you: 转载地址：http://lhfai.baihongyu.com/