poj1860 & poj2240(Bellman-Ford)

1860的思路是将可以换得的不同种的货币的数量当作节点，每个兑换点当成边，然后我抄了个算法导论里面的Bellman-Ford算法，一次就过了。看discussion里面很多讨论精度的，我想都没想过……

2240是更简单的一个bellman-ford，基本和1860一样，就只多了个map容器的应用而已。

以下是1860：

#include <iostream>

using namespace std;

struct Point{

    int a, b;

    double Rab, Cab, Rba, Cba;

};

int main()

{

    int n, m, s;

    double money;

    Point point[];

    cin >> n >> m >> s >> money;

    for (int i = ; i < m; i++){

        cin >> point[i].a >> point[i].b

            >> point[i].Rab >> point[i].Cab

            >> point[i].Rba >> point[i].Cba;

    }

    double node[];

    memset(node, , sizeof(node));

    node[s] = money;

    for (int j = ; j <= n - ; j++){

        for (int i = ; i < m; i++){

            if (node[point[i].a] < (node[point[i].b] - point[i].Cba) * point[i].Rba)

                node[point[i].a] = (node[point[i].b] - point[i].Cba) * point[i].Rba;

            if (node[point[i].b] < (node[point[i].a] - point[i].Cab) * point[i].Rab)

                node[point[i].b] = (node[point[i].a] - point[i].Cab) * point[i].Rab;

        }

    }

    bool flag = true;

    for (int i = ; i < m; i++){

        if (node[point[i].a] < (node[point[i].b] - point[i].Cba) * point[i].Rba

            || node[point[i].b] < (node[point[i].a] - point[i].Cab) * point[i].Rab){

            flag = false;

            break;

        }

    }

    cout << (flag ? "NO" : "YES") << endl;

    return ;

}

2240：

#include <iostream>

#include <map>

#include <string>

using namespace std;

struct Edge{

    int type1, type2;

    double rate;

};

int main()

{

    int n;

    int testCase = ;

    while (cin >> n && n != ){

        double node[];

        Edge edge[];

        map<string, int> currency;

        for (int i = ; i < n; i++){

            string type;

            cin >> type;

            currency[type] = i;

        }

        int m;

        cin >> m;

        for (int i = ; i < m; i++){

            string type1, type2;

            double r;

            cin >> type1 >> r >> type2;

            edge[i].type1 = currency[type1];

            edge[i].type2 = currency[type2];

            edge[i].rate = r;

        }

        for (int i = ; i < n; i++){

            node[i] = ;

        }

        node[] = ;

        for (int i = ; i <= n - ; i++){

            for (int j = ; j < m; j++){

                double tmp = node[edge[j].type1] * edge[j].rate;

                if (node[edge[j].type2] < tmp){

                    node[edge[j].type2] = tmp;

                }

            }

        }

        bool flag = false;

        for (int i = ; i < m; i++){

            if (node[edge[i].type2] < node[edge[i].type1] * edge[i].rate){

                flag = true;

                break;

            }

        }

        cout << "Case " << testCase << ": " << (flag ? "Yes" : "No") << endl;

        testCase++;

    }

    return ;

}