题目：给出几个国家，并给出每个国家之间的汇率，求这几个国家构成的图中所形成的环中，问是否存在套汇的可能，即自身汇率大于1
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <map> 6 #include <algorithm> 7 using namespace std; 8 #define N 35 9 #define M 1000 10 map<string,int> mp; //map 映射 11 struct Edge 12 { 13 int u; 14 int v; 15 double w; 16 }edge[M]; // 结构体存边 17 double dis[N]; //源点i到各点的最长路径,包括到他本身 18 int n,m; 19 bool Bellman_Ford(int st) // 跑一遍BF 20 { 21 for(int i=0; i<n; i++) //记得要初始化 22 dis[i] = 0.0; 23 dis[st] = 1; //刚开始是1 24 for(int i=1; i<=n; i++) //因为源点自己到自己，最多可以经过n个点，所以要<=n 25 { 26 for(int j=0; j<m; j++) //判断每条边，加入它是否可以使最大距离增加 27 { 28 if(dis[edge[j].u] * edge[j].w > dis[edge[j].v] ) 29 dis[edge[j].v] = dis[edge[j].u]*edge[j].w; 30 } 31 } 32 if(dis[st] > 1.0) return 1; // 存在套汇,return 1 33 return 0; 34 } 35 36 int main() 37 { 38 int cas = 1; 39 while(scanf("%d",&n)&&n) 40 { 41 string s; 42 for(int i=0; i<n; i++) 43 { 44 cin>>s; 45 mp[s] = i; 46 } 47 scanf("%d",&m); 48 string s1,s2; 49 double w; 50 for(int i=0; i<m; i++) 51 { 52 cin>>s1>>w>>s2; 53 int u = mp[s1] ; 54 int v = mp[s2] ; 55 edge[i].u = u ; edge[i].v = v ; edge[i].w = w; 56 } 57 int flag = 0; 58 for(int i=0; i<n; i++) // 以每个点为源点跑一遍BF 59 { 60 if(Bellman_Ford(i)) 61 { 62 flag = 1; 63 break; 64 } 65 } 66 if(flag) printf("Case %d: Yes ",cas++); 67 else printf("Case %d: No ",cas++); 68 } 69 return 0; 70 } 71