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;
}