剛開始的時候我不知道這一題該如何來做，我當(dāng)時想到了用搜索，但是數(shù)據(jù)量太大，可能會超時。隊友這一題說可以用最短路徑的方法來做。我實在是想不起來如何做，因為最短路徑的算法我只學(xué)了Dijsktra。我在網(wǎng)上搜了一下，發(fā)現(xiàn)別人用的全是Floyd算法。我就學(xué)習(xí)了一下Floyd。其精髓就是一個三重循環(huán)。以最外層變量為中樞點。不斷的求得兩個點之間的最短路徑。現(xiàn)在我只理解到了這里，有待于以后的提高！
對于這一題，只要能夠找到一個頂點，讓他的值比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 ;
}