ZOJ 1092 Arbitrage Floyd算法
简单的Floyd算法的使用,初始时map对角线上置为1,使用floyd算法处理后只需检查对角线上有没有大于1的,有则赚到了(*^__^*) !#include<stdio.h> #include<string.h> int main(void) { int n,t,i,j,k,x,y,count = 1; char c[32][35],temp1[35],temp2[35]; double map[32][32],price; while(scanf("%d",&n)&&n) { for(i=1;i<=n;i++) scanf("%s",c[i]); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j] = 0.0; } map[i][i] = 1;//初始为1 } scanf("%d",&t); while(t--) { scanf("%s %lf %s",temp1,&price,temp2); for(i=1,j=0;i<=n&&j<=2;i++) { if(strcmp(temp1,c[i]) == 0) { x = i; j ++;//j的作用是使循环提前结束,学到了哈,不然就浪费了time啊! } if(strcmp(temp2,c[i]) == 0) { y = i; j++; } } map[x][y] = price; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j] < map[i][k]*map[k][j]) map[i][j] = map[i][k] * map[k][j]; int flag = 1; for(i=1;i<=n;i++) if(map[i][i] > 1) { printf("Case %d: Yes\n",count++); flag = 0; break; } if(flag) printf("Case %d: No\n",count++); } return 0; } #include<stdio.h> #include<string.h> int main(void) { int n,t,i,j,k,x,y,count = 1; char c[32][35],temp1[35],temp2[35]; double map[32][32],price; while(scanf("%d",&n)&&n) { for(i=1;i<=n;i++) scanf("%s",c[i]); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map[i][j] = 0.0; } map[i][i] = 1;//初始为1 } scanf("%d",&t); while(t--) { scanf("%s %lf %s",temp1,&price,temp2); for(i=1,j=0;i<=n&&j<=2;i++) { if(strcmp(temp1,c[i]) == 0) { x = i; j ++;//j的作用是使循环提前结束,学到了哈,不然就浪费了time啊! } if(strcmp(temp2,c[i]) == 0) { y = i; j++; } } map[x][y] = price; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j] < map[i][k]*map[k][j]) map[i][j] = map[i][k] * map[k][j]; int flag = 1; for(i=1;i<=n;i++) if(map[i][i] > 1) { printf("Case %d: Yes\n",count++); flag = 0; break; } if(flag) printf("Case %d: No\n",count++); } return 0; }
补充:软件开发 , C++ ,