本文共 1256 字，大约阅读时间需要 4 分钟。
给n种货币，和m种货币汇率。
问能否通过汇率是总金额增加。
和POJ-1860相同，都是求正权回路。此题货币由字符串给出，所以可以用map记录字符串对应的标号。
操作方便。
#include #include #include #include #include #include #include #include #include using namespace std;const int MAXN = 30+5;struct Node{ int l,r; double rate;}node[MAXN*MAXN];double Dis[MAXN];int n,m;map name;bool bellman_ford(){ memset(Dis,0,sizeof(Dis)); Dis[1] = 1; for (int i = 1;i<=n-1;i++) { bool flag = false; for (int j = 1; j <= m; j++) if (Dis[node[j].r] < Dis[node[j].l] * node[j].rate) { Dis[node[j].r] = Dis[node[j].l] * node[j].rate; flag = true; } if (!flag) break; } for (int i = 1;i <= m;i++) if (Dis[node[i].r] < Dis[node[i].l] * node[i].rate) return true; return false;}int main(){ string s; double rate; int cnt = 0; while (cin >> n&&n) { for (int i = 1;i<=n;i++) { cin >> s; name[s] = i; } cin >> m; for (int i = 1;i<=m;i++) { cin >> s; node[i].l = name[s]; cin >> rate; node[i].rate = rate; cin >> s; node[i].r = name[s]; } if (bellman_ford()) printf("Case %d: Yes\n",++cnt); else printf("Case %d: No\n",++cnt); } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10276376.html