ZOJ 1092 POJ 2240 Arbitrage Floyd

裸的Floyd做，感觉Floyd复杂度还挺高的，有O（n^3）,适合顶点少的情形。

这里先是求任意两种钱的汇率的最大值，就是一单位这种钱能换多少单位那种钱的最大的换法。在算路径时用乘法不用加法，对角线上的元素为1，自己换自己当然是1，不能换的取值为0，最后对角线上的值大于1了输出yes,否则输出no.

贴代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define INF 1000000
 4 #define MAXN 32
 5 double A[MAXN][MAXN];
 6 int n;
 7 void Floyd()
 8 {
 9     int i,j,k;
10     for(k=0; k<n; k++)
11         for(i=0; i<n; i++)
12             for(j=0; j<n; j++)
13                 if(A[i][k]*A[k][j] > A[i][j])
14                     A[i][j] = A[i][k]*A[k][j];
15 }
16 int main()
17 {
18 //    freopen("in.cpp","r",stdin);
19     int ser = 0;
20     while(~scanf("%d",&n ) && n != 0)
21     {
22         int i,j,k;
23         int m;
24         char c1[50],c2[50];
25         char a[32][50];
26         double cij;
27         for(i=0; i<n; i++)
28             scanf("%s",a[i]);
29         scanf("%d",&m);
30         for(i=0; i<n; i++)
31         {
32             for(j=0; j<n; j++)
33             {
34                 if(i == j) A[i][j] = 1;
35                 else A[i][j] = 0;
36             }
37         }
38         for(i =0; i<m; i++)
39         {
40             scanf("%s",c1);
41             scanf("%lf",&cij);
42             scanf("%s",c2);
43             for(j=0; strcmp(c1,a[j]) != 0; j++);
44             for(k=0; strcmp(c2,a[k]) != 0; k++);
45             A[j][k] = cij;
46         }
47         Floyd();
48         for(i=0; i<n; i++)
49         {
50             if(A[i][i] > 1)
51                 break;
52         }
53         printf("Case %d: ",++ser);
54         if(i == n) printf("No\n");
55         else printf("Yes\n");
56     }
57     return 0;
58 }