ARBITRAG - Arbitrage

xieyikai2333 · 2022-02-03 20:17:17 · 题解

• 题目传送门

• 本篇题解使用 SPFA 跑最长路判正环来做

具体做法

对于每组数据：

1. 存图；

2. SPFA 跑最长路；

3. 如果一个点入队次数超过 n 次，那么有正环，输出 Yes；否则输出 No。

注意：

• 跑最长路时，边权应当相乘而不是相加；

• 本题有多组数据，所以每次一定要清空数组。

代码实现

AC 代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,double> PID;
int n,cnt[35];
bool vis[35];
double dis[35];
map<string,int> mp;
vector<PID> nodes[35];
queue<int> q;
void SPFA(int s)
{
    memset(dis,0,sizeof(dis));
    memset(vis,false,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    dis[s]=1;
    q.push(s);
    vis[s]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(++cnt[u]>n)
        {
            cout<<"Yes\n";
            return;
        }
        vis[u]=false;
        for(PID x:nodes[u])
        {
            int v=x.first;
            double w=x.second;
            if(dis[v]<dis[u]*w)
            {
                dis[v]=dis[u]*w;
                if(!vis[v])
                {
                    q.push(v); 
                    vis[v]=true;
                }
            }
        }
    }
    cout<<"No\n";
    return;
}
void solve()
{
    int m;
    for(int i=0;i<=n;i++)nodes[i].clear();
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        mp[s]=i;
        nodes[0].push_back(make_pair(i,1));
    }
    cin>>m;
    while(m--)
    {
        string u,v;
        double w;
        cin>>u>>w>>v;
        nodes[mp[u]].push_back(make_pair(mp[v],w));
    }
    SPFA(0);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for(int i=1;cin>>n&&n!=0;i++)cout<<"Case "<<i<<": ",solve();
    return 0;
}