Description
Input
Output
Sample Input
3 2 1 20.0 1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00
Sample Output
YES
题目意思:有n种货币,货币之间按照汇率交换,当然还要花费一些手续费,货币交换是可以多次重复进行的,问有没有可能经过一系列的货币交换,开始的货币会增加?
当你用100A币交换B币时,A到B的汇率是29.75,手续费是0.39,那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。
解题思路:这道题可以抽象为图论中的题,将货币种类看为点,货币之间的交换看为有向边,想要货币的金额产生增加,那么必然要有正权回路,即在一条回路上能够一直松弛下去。该题的问题主要在于所给的参数很多,第一行给出了n种货币有m种交换方式,给你第s种货币有V的金额,对于m种的交换方式,从x到y需要汇率rate和手续费commission,从y到x也需要这两个参数。同时这里的松弛递推公式也要发生变化:
if(dist[edge[i].t]<(dist[edge[i].f]-edge[i].c)*edge[i].r) { dist[edge[i].t]=(dist[edge[i].f]-edge[i].c)*edge[i].r; }
因为是需要增加的正权回路,所以如果小于就松弛。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define inf 0x3f3f3f3f struct Edge { int f; int t; double r; double c; } edge[1010]; double dist[605]; int n,m,s,cnt; double x; int bellman_ford() { int i,j; int flag; for(i=1; i<=n; i++) { dist[i]=0; } dist[s]=x; for(j=1; j<=n; j++) { flag=0; for(i=1; i<=cnt; i++) { if(dist[edge[i].t]<(dist[edge[i].f]-edge[i].c)*edge[i].r) { dist[edge[i].t]=(dist[edge[i].f]-edge[i].c)*edge[i].r; flag=1; } } if(flag==0) { break; } } return flag; } int main() { int i,t; int u,v; double a1,a2,b1,b2; while(scanf("%d%d%d%lf",&n,&m,&s,&x)!=EOF) { cnt=1; while(m--) { scanf("%d%d%lf%lf%lf%lf",&u,&v,&a1,&b1,&a2,&b2); edge[cnt].f=u; edge[cnt].t=v; edge[cnt].r=a1; edge[cnt++].c=b1; edge[cnt].f=v; edge[cnt].t=u; edge[cnt].r=a2; edge[cnt++].c=b2; } if(bellman_ford()) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }
附上使用SPFA的代码
#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int INF = 0x3f3f3f3f; const int maxs = 1e3+200; int n,m; struct Edge { int to; double rate; double com; } ; double dis[maxs]; int vis[maxs]; int cnt[maxs];///用来记录入队列次数 vector<Edge>maps[maxs]; void AddEdge(int u,int v,double r,double co) { Edge t; t.to=v; t.rate=r; t.com=co; maps[u].push_back(t); } int SPFA(int s, double v) { int i; memset(dis,0,sizeof(0)); memset(vis,0,sizeof(0)); memset(cnt,0,sizeof(0)); queue<int>q; dis[s]=v; vis[s]=1; cnt[s]++; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(i=0; i<maps[u].size(); i++) { int to=maps[u][i].to; double com=maps[u][i].com; double rate=maps[u][i].rate; if(dis[to]<(dis[u]-com)*rate) { dis[to]=(dis[u]-com)*rate; if(!vis[to]) { vis[to]=1; cnt[to]++; if(cnt[to]>=n) { return 1; } q.push(to); } } } } return 0; } int main() { int s,i; double k; while(scanf("%d%d%d%lf",&n,&m,&s,&k)!=EOF) { int a,b; double c,d,e,f; while(m--) { scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f); AddEdge(a,b,c,d); AddEdge(b,a,e,f); } if(SPFA(s,k)) { puts("YES"); } else { puts("NO"); } } return 0; }