货币套汇（图路径）

科技前沿 • 2025-03-05 21:54 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

题目描述

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

输入

第一行：测试数据组数每组测试数据格式为：
第一行：正整数n (1< =n< =30)，正整数m，分别表示n种货币和m种不同的货币兑换率。
2~n+1行，n种货币的名称。
n+2~n+m+1行，每行有3个数据项ci，rij 和cj ，表示货币ci 和cj的兑换率为 rij。

输出

样例输入

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

样例输出

#include <iostream> #include <string> using namespace std; class Graph { 
    private: int vexnum; //顶点数 int arcnum; //边数 bool *visit; //访问数组 double **array; //邻接矩阵 string *vex; //边 int *road; //记录走过的路 int num; void DFS(int v) { 
    } int Index(string s) { 
    for (int i = 0; i < vexnum; i++) { 
    if (vex[i] == s) { 
    return i; } } return -1; } public: Graph() { 
    cin >> vexnum >> arcnum; vex = new string[vexnum]; visit = new bool[vexnum]; road = new int[vexnum]; array = new double *[vexnum]; for (int i = 0; i < vexnum; i++) { 
    cin >> vex[i]; array[i] = new double[vexnum]; visit[i] = 0; road[i] = 0; for (int j = 0; j < vexnum; j++) { 
    array[i][j] = 0; } } for (int i = 0; i < arcnum; i++) { 
    string str1, str2; double weight; cin >> str1 >> weight >> str2; int pos1 = Index(str1), pos2 = Index(str2); array[pos1][pos2] = weight; } } ~Graph() { 
    delete[] vex; delete[] road; delete[] visit; for (int i = 0; i < vexnum; i++) { 
    delete array[i]; } delete array; } void DFS(int v) { 
    visit[v] = true; road[num++] = v; //记录每一条经过的边，以便后面的计算 for (int i = 0; i < vexnum; i++) { 
    if (visit[i] == 0 && array[v][i] != 0) //若无访问且有边相接，继续遍历 { 
    DFS(i); } } } void DFS_Traverse() { 
    for (int i = 0; i < vexnum; i++) { 
    num = 0; DFS(i); for (int k = 0; k < num; k++) { 
    //判断与起点是否构成环，若构成环则进行计算操作 if (array[road[k]][i] != 0) { 
    double result = 1; for (int j = 0; j < k; j++) { 
    result *= array[road[j]][road[j + 1]]; //一直乘到最后一个点 } result *= array[road[k]][road[0]]; //最后从最后一个点回到起点，构成一个环，将其乘起来 if(result>1) { 
    cout<<"YES"<<endl; } } } } for(int i=0;i<vexnum;i++) { 
    visit[i]=0; road[i]=0; } cout<<"NO"<<endl; } }; int main() { 
    int t; cin>>t; while(t--) { 
    Graph G; G.DFS_Traverse(); } return 0; }

讯享网

货币套汇（图路径）

题目描述

输入

输出

样例输入

样例输出

相关推荐