//附上程序 简单的迭代实现 不过试了很多参数才AC
#include<stdio.h>
#include<string.h>
#define MaxN 21
#define Profit 1.01

int n;
double map[MaxN][MaxN];
double arb[MaxN][MaxN];
int way[MaxN][MaxN][MaxN];
int from,to,len;

int init()
{ int i,j;
 if (scanf("%d",&n)==EOF) return 0;
 for (i=0; i<n; i++)
  for (j=0; j<n; j++)
   {if (i==j) map[i][j]=1; else scanf("%lf",&map[i][j]);
    arb[i][j]=map[i][j]; way[i][j][0]=j;
   }
 return 1;
}

void search()
{ int i,j,k,h;
  double tmp[MaxN][MaxN];
  int tmpw[MaxN][MaxN][MaxN];
 from=-1; to=-1; len=-1;
 for (j=0; j<n; j++)
  for (k=0; k<n; k++)
   if (arb[j][k]*map[k][j]>Profit)
    {from=j; to=k; len=0; return;}
 for (i=1; i<=n-2; i++)
  {memcpy(tmp,arb,sizeof(arb));
   memcpy(tmpw,way,sizeof(way));
   for (j=0; j<n; j++)
    for (k=0; k<n; k++) arb[j][k]=-1;
   for (j=0; j<n; j++)
    for (h=0; h<n; h++)
     for (k=0; k<n; k++)
      if (tmp[j][k]*map[k][h]>arb[j][h])
       {arb[j][h]=tmp[j][k]*map[k][h];
	memcpy(way[j][h],tmpw[j][k],sizeof(tmpw[j][k]));
	way[j][h][i]=h;
       }
   for (j=0; j<n; j++)
    for (k=0; k<n; k++)
     if (arb[j][k]*map[k][j]>Profit)
      {from=j; to=k; len=i; return;}
  }
}

void show()
{ int k;
 if (len==-1) printf("no arbitrage sequence exists\n");
 else
  {printf(" %d",from+1);
   for (k=0; k<=len; k++) printf(" %d",way[from][to][k]+1);
   printf(" %d\n",from+1);
  }
}

int main()
{while(init())
  {search();
   show();
  }
 return 0;
}
 

• 想要通过的同学就想办法让第二个样例输入“ 1 4 3 1” (1629) rruucc 2003-09-13 11:34:54
• 数据有问题吗？ (0) hawk 2003-09-13 15:06:22
  • 没问题 不过这题的special judge是必须的 而且数据中对应的样例那项输出和样例也不一样 难怪那么多人错 建议再加点限制条件并修改数据 或者加special judge (0) rruucc 2003-09-13 15:41:42