1) 實質就是是確定圖中是否存在正環--沿著這個環一直走能夠使環內節點的權值無限增長.
2) 特點是: 每個邊的權值是動態變化的, 這點提醒我們適合用Bellman Ford算法來處理(SPFA實質上是Bellman Ford的優化, 算法思想是一樣的).
SPFA算法:
1
#include <cstdio>
2#include <queue>
3using namespace std;
4
5#define EXPNTNUM (100 + 10)
6#define CURNUM (100 + 10)
7
8
struct Node 
{
9
int to;
10 Node* next;
11 double commission, ratio;
12
};
13
14Node nodeHead[CURNUM + 1];
15Node edge[EXPNTNUM * 2 + 2];
16int pos = 0;
17Node* getEdge() {
18 return edge + pos++;
19}
20
21double maxWeight[CURNUM + 1];
22
23void addEdge(int from, int to, double ratio, double commission) {
24 Node* e = getEdge();
25 Node* n = nodeHead + from;
26 e->to = to;
27 e->ratio = ratio;
28 e->commission = commission;
29 e->next = n->next;
30 n->next = e;
31}
32
33int main() {
34 int currencyNum, pointNum, currencyNumHas;
35 int i, j, a, b;
36 double ratioab, ratioba, comab, comba;
37 double currencisHas;
38
39 scanf("%d%d%d%lf", ¤cyNum, &pointNum, ¤cyNumHas, ¤cisHas);
40
for (i = 1; i <= currencyNum; ++i) {
41 maxWeight[i] = 0;
42 nodeHead[i].next = NULL;
43
}
44 for (i = j = 0; i < pointNum; ++i) {
45 scanf("%d%d", &a, &b);
46 scanf("%lf%lf%lf%lf", &ratioab, &comab, &ratioba, &comba);
47 addEdge(a, b, ratioab, comab);
48 addEdge(b, a, ratioba, comba);
49 }
50
51 maxWeight[currencyNumHas] = currencisHas;
52
53 queue<int> q;
54 q.push(currencyNumHas);
55 int maxEdgeCount = 0;
56 while (true) {
57 int u = q.front();
58 q.pop();
59 for (Node* tra = nodeHead[u].next; tra != NULL; tra = tra->next) {
60 double temp = (maxWeight[u] - tra->commission) *
61 tra->ratio;
62 if (maxWeight[tra->to] < temp) {
63 maxWeight[tra->to] = temp;
64 q.push(tra->to);
65 }
66 }
67 maxEdgeCount++;
68 if (maxWeight[currencyNumHas] > currencisHas) {
69 printf("YES\n");
70 break;
71 }
72 if (q.empty()) {
73 printf("NO\n");
74 break;
75 }
76 }
77
78
79 return 0;
80}
81 Bellman Ford算法:
1#include <cstdio>
2using namespace std;
3
4#define EXPNTNUM (100 + 10)
5#define CURNUM (100 + 10)
6
7struct Edge {
8 int from, to;
9 double commission, ratio;
10};
11
12Edge edge[EXPNTNUM * 2 + 2];
13
14double maxWeight[CURNUM + 1];
15
16void setEdge(Edge &e, int from, int to, double ratio, double commission) {
17 e.from = from;
18 e.to = to;
19 e.ratio = ratio;
20 e.commission = commission;
21}
22
23int main() {
24 int currencyNum, pointNum, currencyNumHas;
25 int i, j, a, b;
26 double ratioab, ratioba, comab, comba;
27 double currencisHas;
28
29 scanf("%d%d%d%lf", ¤cyNum, &pointNum, ¤cyNumHas, ¤cisHas);
30 for (i = j = 0; i < pointNum; ++i) {
31 scanf("%d%d", &a, &b);
32 scanf("%lf%lf%lf%lf", &ratioab, &comab, &ratioba, &comba);
33 setEdge(edge[j++], a, b, ratioab, comab);
34 setEdge(edge[j++], b, a, ratioba, comba);
35 }
36
37 int edgeCount = j;
38 for (i = 1; i <= currencyNum; ++i) {
39 maxWeight[i] = 0;
40 }
41 maxWeight[currencyNumHas] = currencisHas;
42
43 int maxEdgeCount = 0;
44 bool improved;
45 while (true) {
46 improved = false;
47 for (i = 0; i < edgeCount; ++i) {
48 if (maxWeight[edge[i].from] <= 0) {
49 continue;
50 }
51 double temp = (maxWeight[edge[i].from] - edge[i].commission) *
52 edge[i].ratio;
53 if (maxWeight[edge[i].to] < temp) {
54 maxWeight[edge[i].to] = temp;
55 improved = true;
56 }
57 }
58 maxEdgeCount++;
59 if (maxWeight[currencyNumHas] > currencisHas) {
60 printf("YES\n");
61 break;
62 }
63 if (!improved) {
64 printf("NO\n");
65 break;
66 }
// 1) 在提交時不要這個也不會很慢
// 2) 下面代碼的意思是: 在已經插入了currencyNum(節點數)個邊的前提下,
// 如果圖中不存在正回路(這個正回路會使回路內的節點權值無限增加,
// 從而能夠通過兌換貨幣的形式賺錢),
// 則再插入邊不會使任意一個節點的權值增加. 反過來,
// 如果已經插入了currencyNum條邊, 還能插入邊使節點權值增加,
// 則圖中存在正回路.
// 3) 這個終止條件可以使外層while循環至多在currencyNum次后結束.
// 以避免回路權值增長很慢導致循環很多次的極端情況.
67 if (maxEdgeCount > currencyNum && improved) {
68 printf("YES\n");
69 break;
70 }
71 }
72
73 return 0;
74}
75
76