随笔 - 19, 文章 - 0, 评论 - 2, 引用 - 0
数据加载中……

zoj1092_Arbitrage

        刚开始的时候我不知道这一题该如何来做,我当时想到了用搜索,但是数据量太大,可能会超时。队友这一题说可以用最短路径的方法来做。我实在是想不起来如何做,因为最短路径的算法我只学了Dijsktra。我在网上搜了一下,发现别人用的全是Floyd算法。我就学习了一下Floyd。其精髓就是一个三重循环。以最外层变量为中枢点。不断的求得两个点之间的最短路径。现在我只理解到了这里,有待于以后的提高!
       对于这一题,只要能够找到一个顶点,让他的值比1大,就说明可以钱生钱。

#include <stdio.h>
#include 
<string.h>
#include 
<memory.h>
#define DEBUG 1
int n ;
char mo[31][30] ;
double map[31][31] ; 

int Find( char *t )
{
    
int i ;
    
for( i=1; i<=n; ++i )
        
if!strcmp( mo[i], t ) )
            
return i ;
}


void Floyd( )
{
    
int i, j, k ;
    
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] ;
}


void In( )
{
    
int i, x, y, sets ;
    
char a[30], b[30] ;
    
double rate ;
    
for( i=1; i<=n; ++i )
           scanf(
"%s", mo[i] ) ;
    scanf(
"%d"&sets ) ;
    
for( i=1; i<=sets; ++i ){
        scanf(
"%s %lf %s", a, &rate, b ) ;
        x 
= Find( a ) ;
        y 
= Find( b ) ;
        map[x][y] 
= rate ;
    }

}


void Judge( )
{
    
int flag, i ;
    flag 
= 0 ;
    
for( i=1; i<=n; ++i ){
        
if( map[i][i] >= 1 ){
            flag 
= 1 ;
            
break ;
        }

    }

    
if( flag )
        printf(
"Yes\n") ;
    
else
        printf(
"No\n") ;    
}


int main()
{
    
#if DEBUG
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\in.in","r",stdin) ;
    freopen(
"C:\\Documents and Settings\\Administrator\\桌面\\out.out","w",stdout) ;
    
#endif
    
    
int i ;
    
for( i=1; scanf("%d"&n) && n; ++i ){
        printf(
"Case %d: ", i ) ;
        memset( map, 
0sizeof(map) ) ;
        In( ) ;
        Floyd( ) ;
        Judge( ) ;
    }

    
return 0 ;
}

posted on 2009-05-08 00:47 祝你好运! 阅读(219) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理