题解 P1931 【套利】

· · 题解

把汇率表抽象成一个有向图，每个货币是一个结点，每条边上的权值就是汇率。

无法套利的情况分两种

1、没有环，即最后无法回到该种货币

2、有环，但是得到的利率不大于1

我们可以跑一遍单源最长路，用SPFA来判环，只是一般的松弛条件中的加号需要改成乘号。

可以证明如果环上所有边的权值之积大于1，那么一定可以用SPFA判定出有向图中存在环


(
#include <map>
#include <deque>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const size_t Max_N(35);
const size_t Max_M(10000);

size_t Adj[Max_M], Next[Max_M], Head[Max_N];
double Weight[Max_M];

double Dist[Max_N];
bool In_queue[Max_N];
unsigned int Times[Max_N];

unsigned int n, m;

unsigned int fu;

bool spfa(const size_t &S)
{
    memset(Dist, 0, sizeof(Dist));
    memset(In_queue, 0, sizeof(In_queue));
    memset(Times, 0, sizeof(Times));
    std::deque<size_t> Q;

    Dist[S] = 1.0;
    In_queue[S] = true;
    Q.push_back(S);
    Times[S] = 1;

    while (!Q.empty())
    {
        size_t top = Q.front();
        In_queue[top] = false;
        Q.pop_front();

        for (int i = Head[top];i != 0;i = Next[i])
            if (Dist[Adj[i]] < Dist[top] * Weight[i])
            {
                Dist[Adj[i]] = Dist[top] * Weight[i];
                if (!In_queue[Adj[i]])
                {
                    In_queue[Adj[i]] = true;
                    Q.push_back(Adj[i]);
                    ++Times[Adj[i]];
                    if (Times[Adj[i]] >= n)
                        return true;
                }
            }
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        unsigned int tot = 0;
        ++fu;
        memset(Adj, 0, sizeof(Adj));
        memset(Next, 0, sizeof(Next));
        memset(Head, 0, sizeof(Head));
        memset(Weight, 0, sizeof(Weight));
        map<string, unsigned int> v;
        string b, e;
        double number;
        for (unsigned int i = 1;i <= n;++i)
            v[(cin >> b), b] = i;
        cin >> m;
        while (m--)
        {
            ++tot;
            cin >> b >> number >> e;
            Adj[tot] = v[e];
            Weight[tot] = number;
            Next[tot] = Head[v[b]];
            Head[v[b]] = tot;
        }
        for (unsigned int i = 1;i <= n;++i)
            if (spfa(i))
            {
                printf("Case %u: Yes\n", fu);
                goto loop;
            }
        printf("Case %u: No\n", fu);
        loop:
            ;
    }

    return 0;
}
)