题目：一共N个货币种类，当前为S种类的货币，当前拥有的该货币价值为V，下面M行包含可以交换货币的汇率/手续费信息：A,B,RAB,CAB,RBA,CBA分别代表种类A，种类B，A到B的汇率，A到B的手续费，B到A的汇率，B到A的手续费。求能否通过某种交换方式能让货币越来越多即大于V。
解析：Bellman-Ford。修改#1450代码即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<iostream> #include<vector> #include<queue> #define INF 0x3f3f3f3f using namespace std; int n, m, s; float v; struct Currency { Currency() { money = INF; done = false; } //neighbor_index rate commission vector<pair<int, pair<float, float>>> neighbor; float money; bool done; }currency[100]; void SPFA() { queue<int> q; currency[s - 1].money = -v; q.push(s - 1); while (!q.empty()) { int x = q.front(); q.pop(); currency[x].done = false; for (auto ptr = currency[x].neighbor.begin(); ptr != currency[x].neighbor.end(); ptr++) { if (currency[ptr->first].money > -(-currency[x].money - ptr->second.second) * ptr->second.first) { currency[ptr->first].money = -(-currency[x].money - ptr->second.second) * ptr->second.first; if (!currency[ptr->first].done) { currency[ptr->first].done = true; q.push(ptr->first); } } } } if (currency[s - 1].money < v)return; } int main() { //货币种类 下面共几行 当前货币种类 当前拥有的该货币价值 cin >> n >> m >> s >> v; for (int i = 0; i < m; i++) { int a, b; float rab, cab, rba, cba; cin >> a >> b >> rab >> cab >> rba >> cba; currency[a - 1].neighbor.push_back(make_pair(b - 1, make_pair(rab, cab))); currency[b - 1].neighbor.push_back(make_pair(a - 1, make_pair(rba, cba))); } SPFA(); if (-currency[s - 1].money <= v) cout << "NO" << endl; else cout << "YES" << endl; } |
浙公网安备 33010902002953号
Timus这些题目……
原来是同一个学院的吗……