貨幣兌換問題，經(jīng)典問題，這個(gè)問題解決的關(guān)鍵是發(fā)現(xiàn)，如果存在正環(huán)，那么一定是YES。稍微改一下SPFA，尋找一個(gè)圖中的正環(huán)。
1: /**
2: search the longest path , just jude whether there are a positve cycle.
3:
4: */
5:
6: #include <queue>
7: #include <iostream>
8: #include <string.h>
9: #include <stdio.h>
10: using namespace std;
11: #define V 3000 // vertex
12: #define E 1500 // edge
13: #define INF 1000000.0f
14:
15: struct node
16: {
17: int v, next;
18: double R,C,w;
19: }pnt[E];
20:
21: int head[V];
22: double dis[V];
23: bool vis[V];
24: int cnt[V]; // the num of the operation of push to Quque. negatvie cycle.
25: int e = 0; // the index of the edge
26: int N ; // the num of the vertex.
27: int M ; // the num of edges
28: int src, sink;
29: double val;
30: void addedge(int u, int v, double R, double C)
31: {
32: pnt[e].v = v; pnt[e].w= 0;
33: pnt[e].R = R; pnt[e].C = C;
34: pnt[e].next = head[u]; head[u] = e++;
35: }
36: void SPFA_init()
37: {
38: e=0;
39: memset(head, -1,sizeof(head));
40: memset(vis, 0 ,sizeof(vis));
41: memset(cnt, 0 ,sizeof(cnt));
42: for(int i=0; i<=N; i++) dis[i] = 0;
43: }
44: int SPFA()
45: {
46: queue<int> Q;
47: Q.push(src); vis[src] = 1; dis[src] = val; ++cnt[src];
48: while(!Q.empty())
49: {
50: int u = Q.front(); Q.pop(); vis[u] = 0;
51: for(int i=head[u]; i!=-1; i=pnt[i].next)
52: {
53: int v = pnt[i].v;
54: pnt[i].w = (dis[u] - pnt[i].C)*pnt[i].R - dis[u];
55: //cout<<u<<" to "<<v<<" "<<pnt[i].w<<endl;
56: if( dis[v] < dis[u] + pnt[i].w )
57: {
58: dis[v] = dis[u] + pnt[i].w;
59: //cout<<u<<" to "<<v<<" "<<pnt[i].w<<" "<<dis[v]<<endl;
60: if(!vis[v]) { Q.push(v); vis[v] = 1;}
61: if( ++cnt[v] > N) return -1; // negative cycle.
62: }
63: }
64: }
65: return 1;
66: //if(dis[sink] == INF) return -2; // can't from src to sink.
67: //return dis[sink];
68: }
69:
70: int main()
71: {
72: freopen("1860.txt","r",stdin);
73: scanf("%d%d", &N , &M);
74:
75: scanf("%d", &src);
76: //cout<<src<<endl;
77: scanf("%lf", &val);
78: //cout<<val<<endl;
79: SPFA_init();
80: for(int i=0; i<M; i++)
81: {
82: int a, b; double Rab, Cab, Rba,Cba;
83: scanf("%d%d", &a, &b);
84: scanf("%lf%lf", &Rab, &Cab);
85: scanf("%lf%lf", &Rba, &Cba);
86: addedge(a, b,Rab, Cab);
87: addedge(b,a,Rba, Cba);
88: //cout<<Rab<<" "<<Cab<<" "<<Rba<<" "<<Cba<<endl;
89: }
90: int ret = SPFA();
91: if(ret == -1) cout<<"YES"<<endl;
92: else cout<<"NO"<<endl;
93: return 0;
94: }