poj1860 Currency Exchange: spfa / Bellman Ford

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
 8struct 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"&currencyNum, &pointNum, &currencyNumHas, &currencisHas);
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"&currencyNum, &pointNum, &currencyNumHas, &currencisHas);
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


posted on 2011-07-04 09:18 cucumber 阅读(330) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜