POJ 2240 Arbitrage

Posted on | In | 阅读

SPFA找正环或者用Floyd找自己到自己最长路大于1的点

C++ Code

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <map>
#include <queue>
#define M 35
#define INF 80000000

using namespace std;

double arr[M][M];
bool isInqueue[M];
int numInqueue[M];
int num, numedge;
double dis[M];


bool spfa(){
    memset(numInqueue, 0, sizeof(numInqueue));
    memset(isInqueue, 0, sizeof(isInqueue));
    queue<int> q;
    for(int i = 1; i <= num; i++){
        dis[i] = INF;
        q.push(i);
        isInqueue[i] = true;
        numInqueue[i]++;
    }

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        isInqueue[cur] = false;
        for(int i = 1; i <= num; i++){
            if(arr[cur][i] > 0){
                if(dis[i] < dis[cur]*arr[cur][i]){
                    dis[i] = dis[cur] * arr[cur][i];
                    if(!isInqueue[i]){
                        q.push(i);
                        isInqueue[i] = true;
                        numInqueue[i] ++;
                        if(numInqueue[i] >= num)
                            return true;
                    }
                }
            }
        }
    }
    return false;
}

int main(){
    int ca = 1;
    while(scanf("%d", &num) && num != 0){
        memset(arr, 0 , sizeof(arr));
        map<string, int> m;
        string name, c1, c2;
        double rate;
        for(int i = 1; i <= num; i++){
            cin >> name;
            m[name] = i;
        }
        scanf("%d", &numedge);
        for(int i = 1; i <= numedge; i++){
            cin >> c1 >> rate >> c2;
            arr[m[c1]][m[c2]] = rate;
        }
        bool flag = spfa();
        if(flag)
            printf("Case %d: Yes\n", ca++);
        else
            printf("Case %d: No\n", ca++);
    }
    return 0;
}

Floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <stdio.h>
#include <map>
#include <cstring>
#include <string>

using namespace std;
double arr[31][31];

double max(double a, double b)
{
    return a > b ? a : b;
}

int main()
{
    map<string, int> name;
    int num , m;
    int a, b;
    double trans;
    string cash1, cash2;
    int ca = 1;
    while(cin >> num && num)
    {
        memset(arr, 0, sizeof(arr));
        for(int i = 0; i < num; i++)
        {
            cin >> cash1;
            name[cash1] = i;
        }
        cin >> m;
        for(int i = 0; i < m; i++)
        {
            cin >> cash1;
            a = name[cash1];
            cin >> trans;
            cin >> cash2;
            b = name[cash2];
            arr[a][b] = trans;
        }
        for(int k = 0; k < num; k++)
            for(int i = 0; i < num; i++)
                for(int j = 0; j < num; j++)
                    arr[i][j] = max(arr[i][j], arr[i][k]*arr[k][j]);
        bool flag = false;
        for(int i = 0; i < num; i++)
        {
            if(arr[i][i] > 1)
            {
                cout << "Case " << ca++ << ": Yes" <<endl;
                flag = true;
                break;
            }
        }
        if(!flag)
            printf("Case %d: No\n", ca++);
    }
    return 0;
}