首页 > 代码库 > Arbitrage
Arbitrage
点击打开链接
题意:货币兑换,换取最大钱币;
解析:构图,spfa
#include<iostream> #include<cstring> #include<queue> #include<map> #include<cstdio> using namespace std; const int maxn = 1005; double cost[ maxn ][ maxn ], dis[ maxn ]; int vis[ maxn ]; int n, m; char ch[ maxn ], str1[ maxn ], str2[ maxn ]; map<string,int> str; int spfa( int start ){ for( int i = 1; i <= n; ++i ){ dis[ i ] = vis[ i ] = 0; } vis[ start ] = 1; dis[ start ] = 1.0; queue< int > Q; while( !Q.empty() ){ Q.pop(); } Q.push( start ); while( !Q.empty() ){ int p = Q.front(); Q.pop(); vis[ p ] = 0; for( int i = 1; i <= n; ++i ){ if( dis[ p ] * cost[ p ][ i ] > dis[ i ] ){ dis[ i ] = dis[ p ] * cost[ p ][ i ]; if( dis[ start ] > 1.0 ){ return 1; } if( !vis[ i ] ){ vis[ i ] = 1; Q.push( i ); } } } } return 0; } int main(){ int Case = 1; while( scanf( "%d", &n ) != EOF ){ if( !n ) break; str.clear(); for( int i = 1; i <= n; ++i ){ for( int j = 1; j <= n; ++j ){ if( i == j ) cost[ i ][ j ] = 1.0; else cost[ i ][ j ] = 0; } } for( int i = 1; i <= n; ++i ){ scanf( "%s", ch ); str[ ch ] = i; } scanf( "%d", &m ); double num; for( int i = 1; i <= m; ++i ){ scanf( "%s%lf%s", str1, &num, str2 ); cost[ str[ str1 ] ][ str[ str2 ] ] = num; } int flag = 0; for( int i = 1;i <= n; ++i ){ if( spfa( i ) ){ flag = 1; break; } } printf( "Case %d: ", Case++ ); if( flag ){ puts( "Yes" ); } else{ puts( "No" ); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。