题意:套汇问题。问能否套汇盈利。
题解:
#include <cstring> #include <iostream> using namespace std; char cur[31][50]; char str1[50], str2[50]; double arb[31][31]; int n,m; bool floyd () { int i,j,k; for ( k = 0; k < n; k++ ) { for ( i = 0; i < n; i++ ) for ( j = 0; j < n; j++ ) if ( arb[i][j] < arb[i][k] * arb[k][j] ) arb[i][j] = arb[i][k] * arb[k][j]; } for ( i = 0; i < n; i++ ) if ( arb[i][i] > 1 ) return true; return false; } int main() { double num; int i, j, x, y, Case = 1; while ( cin >> n && n != 0 ) { memset(arb,0,sizeof(arb)); for ( i = 0; i < n; i++ ) cin >> cur[i]; cin >> m; for ( i = 0; i < m; i++ ) { cin >> str1 >> num >> str2; for ( j = 0; j < n; j++ ) { if ( strcmp(str1,cur[j]) == 0 ) x = j; if ( strcmp(str2,cur[j]) == 0 ) y = j; } arb[x][y] = num; } if ( floyd () ) cout << "Case " << Case++ << ": Yes" << endl; else cout << "Case " << Case++ << ": No" << endl; } return 0; }