zoj 1092 && poj 2240 Arbitrage (floyd算法)

這道題昨天晚上用dijkstra寫的,但是一直wa,用dijkstra每次找到最大的點之後接着找,後來經人提醒才醒悟,每次找最大的點更新接下來的點得到的并不一定是最大的.于是就想起來用floyd.照着書上的floyd代碼,稍微改了下,AC.

這道題的題意就是通過各國匯率的不同通過進行外币交易來判斷是否能賺錢,如果能夠賺錢,則輸出yes,不能則輸出no.

#include <stdio.h>

#include <string.h>

int n,m,i,j,flag,k,count = 0;

char name[100][100],temp1[50],temp2[50];

double map[100][100],rate,dist[100][100],temp;

void output(int flag)

{//輸出;

if (flag)

printf("Yes/n");

else

printf("No/n");

}

void initmap()

{//初始化map[][];

for (i=0;i<n;i++)

{

for (j=0;j<n;j++)

map[i][j] = 0.0;

map[i][i] = 1.0;

}

}

void input()

{//輸入;

for (i=0;i<n;i++)

scanf("%s",name[i]);

scanf("%d",&m);

while (m--)

{

scanf("%s",temp1);

scanf("%lf",&rate);

scanf("%s",temp2);

for (i=0;i<n;i++)

if ( strcmp(temp1,name[i]) == 0)

break;

for (j=0;j<n;j++)

if ( strcmp(temp2,name[j]) == 0)

break;

map[i][j] = rate;

}

}

void initdist()

{//初始化dist[][];

for (i=0;i<n;i++)

for (j=0;j<n;j++)

dist[i][j] = map[i][j];

}

void floyd()

{//floyd過程;

for (k=0;k<n;k++)

for (i=0;i<n;i++)

for (j=0;j<n;j++)

if (dist[i][j] < dist[i][k]*dist[k][j])

dist[i][j] = dist[i][k]*dist[k][j];

}

int main(void)

{

while (scanf("%d",&n) != EOF && n)

{

flag = 0;

initmap();

input();

initdist();

floyd();

for (i=0;i<n;i++)

if (dist[i][i] > 1.0)

{

flag = 1;

break;

}

printf("Case %d: ",++count);

output(flag);

}

return 0;

}