货币套汇（图路径）

目录

题目描述

思路分析

AC代码

---

题目描述

汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，1法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，确定货币间是否存在套汇的可能性。

提示：判断图上是否出现正环,即环上所有的边相乘大于1

输入

第一行：测试数据组数

每组测试数据格式为：

第一行：正整数n (1< =n< =30)，正整数m，分别表示n种货币和m种不同的货币兑换率。

2~n+1行，n种货币的名称。

n+2~n+m+1行，每行有3 个数据项ci，rij 和cj ，表示货币ci 和cj的兑换率为 rij。

输出

对每组测试数据，如果存在套汇的可能则输出YES

如果不存在套汇的可能，则输出NO。

输入样例1

2
3 3
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3 6
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

输出样例1

YES
NO

思路分析

看起来很简单但是实际写起来跑起来还是有很多问题的。

想法很简单，用DFS去跑完一个回路，判断汇率是否大于1就行，思路是这样的，但是有很多细节需要注意。

一个是图必须是单向图。

避免陷入一个圈不能出来就不能往回走，必须标记已经走过的路，这又涉及到第一个不能标记的问题，因为DFS结束的条件就是找到这个边的终点是起点，所以第一个不能标记。

同时存在回溯的问题，这一步没有解或者是非最优解，那么退回上一步的时候，整个的状态需要恢复回去。

AC代码

#include 
using namespace std;
const int max_vertex_number=100;
class Map{
    float matrix[max_vertex_number][max_vertex_number]={0};
    bool visited[max_vertex_number]={false};
    int vertex_number,edges;
    string vertex[max_vertex_number];
    float max;
public:
    Map(){
        cin>>vertex_number>>edges;
        for(int i=0;i
            cin>>vertex[i];
        for(int i=0;i
            float ratio;
            string head,tail;
            cin>>head>>ratio>>tail;
            matrix[getIndex(head)][getIndex(tail)]=ratio;
        }
    }
    int getIndex(string&data){
        for(int i=0;i
            if(data==vertex[i])
                return i;
    }
    void DFS(int&start,int¤t,float&ratio){
        if(current==start){
            if(max
                max=ratio;
            return;
        }
        for(int i=0;i
            if(visited[i])
                continue;
            if(matrix[current][i]){
                ratio*=matrix[current][i];
                visited[i]=true;
                DFS(start,i,ratio);
                ratio/=matrix[current][i];
                visited[i]= false;
            }
        }
    }
    void Show(){
        max=0;
        for(int i=0;i
            for(int j=0;j
                if(matrix[i][j]){
                    float ratio=matrix[i][j];
                    visited[j]= true;
                    DFS(i,j,ratio);
                    visited[j]= false;
                }
            }
        }
        if(max>1)
            cout<<"YES"<
        else cout<<"NO"<
    }
};
int main() {
    int t;
    cin>>t;
    while(t--){
        Map test;
        test.Show();
    }
}