[kuangbin带你飞] 题单 最短路问题 + 并查集问题模板题及简单题 https://blog.csdn.net/m0_46272108/article/details/108923142
Floyd原理推荐可以看看这篇：https://blog.csdn.net/m0_46272108/article/details/108919125 感觉没什么好讲的。理解Floyd算法就可以了… 这道题是：判断图中是否存在变大环 感觉还可以用其他方法做，下次一定！！！（有空一定更新）
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define ll long long //#define int ll #define inf 0x3f3f3f3f using namespace std; int read() { int w = 1, s = 0; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; //最大公约数 }int gcd(int x,int y) { if(x<y) swap(x,y);//很多人会遗忘，大数在前小数在后 //递归终止条件千万不要漏了，辗转相除法 return x % y ? gcd(y, x % y) : y; } int lcm(int x,int y)//计算x和y的最小公倍数 { return x * y / gcd(x, y);//使用公式 } //------------------------ 以上是我常用模板与刷题几乎无关 ------------------------// const int N = 1010; double Map[N][N]; int n, m,a,b,cnt = 0; char money[N][N]; char money1[N],money2[N]; //纯floyd 算法 void floyd() { for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (Map[i][k] * Map[k][j] > Map[i][j]) { Map[i][j] = Map[i][k] * Map[k][j]; } } } } } int main() { double t; while (~scanf("%d",&n) && n) { ++cnt; memset(Map, inf, sizeof(Map)); for (int i = 0; i < n; ++i) { scanf("%s", money[i]); //一开始的汇率为1 Map[i][i] = 1.0 ; } int m = read(); for (int i = 0;i < m; ++i) { scanf("%s %lf %s", money1, &t, money2); int j; for (j = 0; j < n; ++j) { //如果不同就跳 if (!strcmp(money1, money[j])) { break; } } int k; for (k = 0 ; k < n; ++k) { //如果不同就跳 if (strcmp(money2, money[k]) == 0) { break; } } Map[j][k] = t; } int flag = 0; floyd(); for (int i = 0 ; i < n ; ++i) { //如果自身汇率大于1，说明可以套利 if (Map[i][i] > 1.0) { flag = 1 ; break; } } if(flag) printf("Case %d: Yes\n",cnt); else printf("Case %d: No\n",cnt); } return 0; }