-
Notifications
You must be signed in to change notification settings - Fork 4
/
uva-104.cpp
69 lines (57 loc) · 1.43 KB
/
uva-104.cpp
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
58
59
60
61
62
63
64
65
66
67
68
69
//uva 104
//Arbitrage
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main(void)
{
int n;
while(cin >> n){
vector < vector <double> > arbitrage(n, vector <double> (n));
vector < vector < vector <int> > > parent(n, vector <vector <int> > (n, vector <int> (n, -1)));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j){
if(i == j)
arbitrage[i][j] = 1.0;
else
cin >> arbitrage[i][j];
}
vector < vector <double> > profit = arbitrage;
vector <int> path;
for(int step = 1; step < n; ++step){
vector < vector <double> > new_profit = profit;
for(int k = 0; k < n; ++k)
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(new_profit[i][j] < profit[i][k] * arbitrage[k][j]){
new_profit[i][j] = profit[i][k] * arbitrage[k][j];
parent[step][i][j] = k;
}
profit = new_profit;
for(int p = 0; p < n; ++p)
if(profit[p][p] > 1.01){
int right = p;
path.push_back(p);
for(int s = step; s >= 0; --s)
if(parent[s][p][right] != -1){
path.push_back(parent[s][p][right]);
right = parent[s][p][right];
}
path.push_back(p);
break;
}
if(!path.empty())
break;
}
if(!path.empty()){
cout << path.back() + 1;
for(int i = path.size() - 2; i >= 0; --i)
cout << ' ' << path[i] + 1;
cout << endl;
}
else
cout << "no arbitrage sequence exists" << endl;
}
return 0;
}