104 Arbitrage

简单问题就是从一个国家到另一个国家能套汇超过1.01即可

选用的算法是Floyd-Warshall，稍作修改，状态转移公式是从一个国家i到另一国家j经过次数k能套汇超过1.01

#include 
#include using namespace std;class Arbitrage
{
public:void readArbitrage(const int& iCountry);void computeArbitrage();void outputResult();
private:vector>> m_vecConversionRates;vector>> m_vecSequence;vector m_vecCountry;
};void Arbitrage::readArbitrage(const int& iCountry)
{float fConversionRate;m_vecConversionRates.clear();m_vecSequence.clear();m_vecConversionRates.resize(iCountry);m_vecSequence.resize(iCountry);for (int i = 0; i < iCountry; ++i){m_vecConversionRates[i].resize(iCountry);m_vecSequence[i].resize(iCountry);for (int j = 0; j < iCountry; ++j){m_vecConversionRates[i][j].resize(iCountry);m_vecSequence[i][j].resize(iCountry);}}for (int i = 0; i < iCountry; ++i){for (int j = 0; j < iCountry; ++j){if (i == j){m_vecConversionRates[0][i][j] = 1;}else{cin >> fConversionRate;m_vecConversionRates[0][i][j] = fConversionRate;}m_vecSequence[0][i][j] = i;}}
}void Arbitrage::computeArbitrage()
{m_vecCountry.clear();for (int l = 1; l < m_vecConversionRates.size(); ++l){for (size_t i = 0; i < m_vecConversionRates.size(); ++i){for (size_t j = 0; j < m_vecConversionRates.size(); ++j){for (size_t k = 0; k < m_vecConversionRates.size(); ++k){if (m_vecConversionRates[l][i][j] <= m_vecConversionRates[l - 1][i][k] * m_vecConversionRates[0][k][j]){m_vecConversionRates[l][i][j] = m_vecConversionRates[l - 1][i][k] * m_vecConversionRates[0][k][j];m_vecSequence[l][i][j] = k;if (m_vecConversionRates[l][i][j] > 1.01 && i == j){m_vecCountry.push_back(i);while (l >= 0){m_vecCountry.push_back(m_vecSequence[l][i][j]);j = m_vecSequence[l--][i][j];}return;}}}}}}
}void Arbitrage::outputResult()
{if (m_vecCountry.size() == 0){cout << "no arbitrage sequence exists" << endl;}else{cout << *m_vecCountry.rbegin() + 1;for (auto it = m_vecCountry.rbegin() + 1; it != m_vecCountry.rend(); ++it){cout << " " << *it + 1;}cout << endl;}
}int main()
{Arbitrage objArbitrage;int iCountry = 0;while (cin >> iCountry){objArbitrage.readArbitrage(iCountry);objArbitrage.computeArbitrage();objArbitrage.outputResult();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！