UVA_104

    这个题目实际上是在求一个汇率乘积大于等于1.01的最小环。由于数据量不大，我们可以直接用动规+floyd解决，设f[i][j][k]为由i到j经过k次转换所能达到的最大汇率乘积，每循环一次k我们就扫描一遍f[i][i][k]，如果有大于1.01的情况就直接打印结果即可。

    在记录路径时用path[i][j][k]记录第k次转换的初始位置，打印时采用递归的方式。

#include
     
       #include
      
        #define MAXD 30 #define MAXM 10010 int N, path[MAXD][MAXD][MAXD]; double f[MAXD][MAXD][MAXD]; void init() {
   int i, j;     memset(f, 0, sizeof(f)); for(i = 0; i < N; i ++) for(j = 0; j < N; j ++) if(i != j)             {
                   scanf("%lf", &f[i][j][1]);                 path[i][j][1] = i;             } } void printpath(int i, int j, int p) {
   if(p == 0)         printf("%d", i + 1); else     {
           printpath(i, path[i][j][p], p - 1);         printf(" %d", j + 1);     } } void floyd() {
   int i, j, k, p; for(p = 1; p < N; p ++)     {
   for(k = 0; k < N; k ++) for(i = 0; i < N; i ++) for(j = 0; j < N; j ++) if(f[i][k][p] * f[k][j][1] > f[i][j][p + 1] + 1e-12)                     {
                           f[i][j][p + 1] = f[i][k][p] * f[k][j][1];                         path[i][j][p + 1] = k;                     } for(i = 0; i < N; i ++) if(f[i][i][p + 1] > 1.01)             {
                   printpath(i, i, p + 1);                 printf("\n"); return ;             }     }     printf("no arbitrage sequence exists\n"); } int main() {
   while(scanf("%d", &N) == 1)     {
           init();         floyd();     } return 0; }