刚开始的时候我不知道这一题该如何来做，我当时想到了用搜索，但是数据量太大，可能会超时。队友这一题说可以用最短路径的方法来做。我实在是想不起来如何做，因为最短路径的算法我只学了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, 0, sizeof(map) ) ;
In( ) ;
Floyd( ) ;
Judge( ) ;
}
return 0 ;
}