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