題目鏈接：http://poj.org/problem?id=1860

題意是給你n種貨幣，下面m種交換的方式，擁有第s種貨幣V元。問你最后經過任意轉換可不可能有升值。下面給你貨幣u和貨幣v，r1是u到v的匯率，c1是u到v的手續費，同理r2是v到u的匯率，c2是v到u的手續費。轉換后的錢B = (轉換之前的錢A - c) * r。

我用spfa做的，不斷地松弛。要是存在正環，或者中間過程最初的錢升值了，就說明會升值。有負環的話，不滿足松弛的條件，慢慢地就會彈出隊列，也就不會升值。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 const int MAXN = 1005; 7 struct data { 8 int next , to; 9 double r , c; 10 }edge[MAXN * 3]; 11 int head[MAXN] , cont; 12 double d[MAXN]; 13 14 void init(int n) { 15 for(int i = 0 ; i <= n ; i++) { 16 head[i] = -1; 17 d[i] = 0; 18 } 19 cont = 0; 20 } 21 22 inline void add(int u , int v , double r , double c) { 23 edge[cont].next = head[u]; 24 edge[cont].to = v; 25 edge[cont].r = r; 26 edge[cont].c = c; 27 head[u] = cont++; 28 } 29 30 bool spfa(int s , double V) { 31 queue <int> que; 32 while(!que.empty()) { 33 que.pop(); 34 } 35 que.push(s); 36 d[s] = V; 37 while(!que.empty()) { 38 int temp = que.front(); 39 que.pop(); 40 for(int i = head[temp] ; ~i ; i = edge[i].next) { 41 double x = edge[i].r * (d[temp] - edge[i].c); 42 if(x > d[edge[i].to]) { //松弛 43 d[edge[i].to] = x; 44 que.push(edge[i].to); 45 if(d[s] > V) //增加則直接返回true 46 return true; 47 } 48 } 49 } 50 return false; 51 } 52 53 int main() 54 { 55 int n , m , s , u , v; 56 double V , r , c; 57 while(~scanf("%d %d %d %lf" , &n , &m , &s , &V)) { 58 init(n); 59 for(int i = 0 ; i < m ; i++) { 60 scanf("%d %d %lf %lf" , &u , &v , &r , &c); 61 add(u , v , r , c); 62 scanf("%lf %lf" , &r , &c); 63 add(v , u , r , c); 64 } 65 if(spfa(s , V)) 66 printf("YES\n"); 67 else 68 printf("NO\n"); 69 } 70 }

?

轉載于:https://www.cnblogs.com/Recoder/p/5294974.html

總結

以上是生活随笔為你收集整理的POJ 1860 Currency Exchange (SPFA松弛)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。