poj1741，POJ1860Currency Exchange（SPFA）-變量-匯編語言學習筆記

poj1741，POJ1860Currency Exchange（SPFA）

2023-12-07 阅读 30 评论 0

摘要：http://poj.org/problem?id=1860 題意： ?題目中主要是說存在貨幣兌換點，然后現在手里有一種貨幣，要各種換來換去，最后再換回去的時候看能不能使原本的錢數增多，每一種貨幣都有對應的匯率，而貨幣A到貨幣B的匯率即為1貨幣A換得得

http://poj.org/problem?id=1860

題意： ?題目中主要是說存在貨幣兌換點，然后現在手里有一種貨幣，要各種換來換去，最后再換回去的時候看能不能使原本的錢數增多，每一種貨幣都有對應的匯率，而貨幣A到貨幣B的匯率即為1貨幣A換得得貨幣B的數量，但兌換點是要收取傭金的，且傭金從源貨幣中扣除，例如，你想在匯率29.75，傭金為0.39的兌換點把100美元換成盧布，得到的盧布數即為（100-0.39）*29.75 = 2963.3975.

poj1741，樣例解釋：

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

? ?多組輸入，第一行中N代表有N種貨幣可以互相兌換，M代表有M個貨幣兌換點，S代表這個人手中的的貨幣的編號，V代表這個人手中擁有的貨幣數量，底下M行

每行六個數，A,B代表可以交換的貨幣A和B，剩下的實數RAB,CAB,RBA,CBA，代表A到B的匯率，傭金，B到A的匯率，傭金。以某種兌換方式增加原本的錢數，而且必須兌換為原來的貨幣。

Poj在線評測平臺、解法：用spfa和Bellman都可以，我用的是spfa，改了一下原模板就過了

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 int u,v,w;
 8 const int maxn = 1011;
 9 const int maxm = 10011;
10 const int oo = 1<<29;
11 struct node
12 {
13     int u;
14     int v;
15     double x,y ;
16     int next;
17 }edge[maxm];
18 double dis[maxn];
19 int m,n,num;
20 double ount;
21 int head[maxn],cnt,sum[maxn];
22 int vis[maxn] = {0};
23 queue<int>qu;
24 void add(int u,int v,double x,double y)
25 {
26     edge[cnt].u = u ;
27     edge[cnt].v = v ;
28     edge[cnt].x = x ;
29     edge[cnt].y = y ;
30     edge[cnt].next = head[u];
31     head[u] = cnt++ ;
32 }
33 int spfa(int s)
34 {
35     for(int i = 0 ; i < m ; i++)
36     {
37         dis[i] = 0;
38         vis[i] = 0 ;
39     }
40     dis[s] = ount;
41     qu.push(s);
42     vis[s] = 1 ;
43     while(!qu.empty())
44     {
45         int u = qu.front();
46         qu.pop();
47         vis[u] = 0;
48         for(int i = head[u] ; i != -1 ; i = edge[i].next)
49         {
50             int v = edge[i].v;
51             if((dis[u]-edge[i].y)*edge[i].x > dis[v])
52             {
53                 dis[v] = (dis[u]-edge[i].y)*edge[i].x;
54                 if(!vis[v])
55                 {
56                     vis[v] = 1;
57                     qu.push(v);
58                 }
59                 sum[v]++;
60                 if(sum[v] > m)
61                 return -1;
62             }
63         }
64     }
65     return 1;
66 }
67 void Init()
68 {
69     cnt = 0 ;
70     memset(head,-1,sizeof(head));
71     memset(sum,0,sizeof(sum));
72     while(!qu.empty())
73     qu.pop();
74 }
75 int main()
76 {
77     while(scanf("%d %d %d %lf",&m,&n,&num,&ount)!=EOF)
78     {
79         Init();
80         int u,v;
81         double x,y,xx,yy ;
82         for(int i = 0 ; i < n ; i++)
83         {
84             scanf("%d %d %lf %lf %lf %lf",&u,&v,&x,&y,&xx,&yy);
85             add(u,v,x,y);
86             add(v,u,xx,yy);
87         }
88         if(spfa(num) > 0)
89         cout<<"NO"<<endl;
90         else cout<<"YES"<<endl;
91     }
92     return 0;
93 }