UVA104 Arbitrage

Graph, Dynamic Programming, Floyd

출처: UVA UVA104 Arbitrage


SOL)
DP, Floyd
단순히 이윤이 나는 경로만 계산하면 간단하게 floyd만 구현하면 되지만
1.01보다 커야하는 조건이 있기때문에 dp를 적절하게 써야한다.
점화식 dp[u][v][s] = max(dp[u][k][s-1] * cost[k][v]);
s는 이용한 간선의 수
u,v는 정점
dp[2][3][2] = 정점 2에서 3으로 간선을 2개 이용한 최대 값


[-] Collapse

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int MAX_V = 21;
const int INF = (1 << 30);

int V; //정점의 수
double dp[MAX_V][MAX_V][MAX_V];
int via[MAX_V][MAX_V][MAX_V];

void path(int u, int v, int s)
{
    if (s == 0){
        printf("%d", u);
        return;
    }
    path(u, via[u][v][s], s - 1);
    printf(" %d", v);
}

void floyd(){
    int s;
    for (s = 2; s <= V; s++) //s는 방문 수
    {
        for (int k = 1; k <= V; k++){
            for (int i = 1; i <= V; i++){
                for (int j = 1; j <= V; j++){
                    if (dp[i][j][s] < dp[i][k][s - 1] * dp[k][j][1]) //i에서 j로
                    {
                        dp[i][j][s] = dp[i][k][s - 1] * dp[k][j][1];
                        via[i][j][s] = k;
                        if (i == j && dp[i][j][s] > 1.01) {
                            path(i, i, s);
                            printf("\n");
                            return;
                        }
                    }
                }
            }
        }
    }
    cout << "no arbitrage sequence exists" << endl;
}

int main(){
    //freopen("input.txt", "r", stdin);
    while (cin >> V){
        memset(via, -1, sizeof(via));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= V; i++){
            for (int j = 1; j <= V; j++){
                if (i == j) dp[i][j][1] = 1;
                else cin >> dp[i][j][1];
            }
        }
        floyd();
    }
}