104 - Arbitrage

jd3

題意：給定匯率、求能轉換最少次數、換回原本貨幣的、獲利>=1.01% 的方法


解析(一個禮拜的心路歷程?)：
首先，他是一張有向圖，沒有回到自己的邊，也沒有重邊
要找回到自己的路徑(即環)，路徑長度 從邊的權重相加 改成 相乘
然後是判斷路徑大於1.01以及回復路徑


如果寫過一些有"回到原點"的最短路徑題目
例如： (痾....不見了)
對這題的直覺應該就是 Floyd-Warshall (下簡稱FW)的開心 for迴圈*3
(點的數量也才那麼一點點) (別動 ! 小心 ! )


把他換成全點對的最小路徑來處理，最小路徑換成>1.01的路線裡面更新最少次的


怎麼做呢? 首先我們想到要儲存更新次數和儲存路徑，所以開個陣列來存
for for for 爆下去然後再 for for找了最短的路徑然後再遞迴找答案
或許你覺得(其實是我以為...)一開始自己到自己設成無限大然後回來看就知道有拿裡有>1.01的環了
然後就開心的WA了
(不~可能連範測都沒過OAO)


因為直接FW找出來的答案有點問題 (三層for很爽但是別急別急~)
首先最容易證明的是一個很容易WA掉的一筆測資(很討厭的)
他的答案是 1 2 1 2 1
不~他繞了兩圈!!!
咱們如果只用2維表格下去存，最後遞迴一定找不出來這條路徑


其他的錯誤就例如說誤解FW的表格的意義啦~(並不是說不可以有不同解釋)
更新條件的錯誤啦~(其實我這邊已經錯到很離譜所以接著進入AC解法)



先來瞭解一下FW

[C++] 純文本查看 復制代碼

    for(int k = 0 ; k < n ; k++)    //中繼點 
        for(int i = 0 ; i < n ; i++)
            for(int j = 0 ; j < n ; j++)
                if(dist[i][j] > dist[i][k]+dist[k][j])
                    dist[i][j] = dist[i][k]+dist[k][j];

當準備更新第k次的時候
dist[j]存的是只使用了0~(k-1)之中的點當中繼點(經過)的最短距離(不一定有使用(經過))(不經過k~(n-1))
加入第k個點當作可用的中繼點後如果答案比較好就更新
(關於原本的FW三維表格請自行google)



基於剛才發現到的問題，FW不能用了OAO
因為更新時在原本的矩陣上迭代，資訊被覆蓋了
所以現在把「更新第P次」拉出第3個維度來開表格
每次更新時在新的一層上填入，並記錄前一個點


更新時不使用 if(dist[j] > dist[k]+dist[k][j])
而是改成 if(dist[j][p] > dist[k][p-1]+dist[k][j][0])
( 假設原本的圖存在dist[j][0] )
請注意紅字的 0
+dist[k][j][0] 確保更新P次只經過P個點



見下方code的SP()
P的for迴圈包在更新外面，表示更新第P次
更新完立即檢察是否有符合條件的環可以快一些


雖然此題用這方法不考慮浮點誤差也會AC
但也可以用log()取值後路徑長就變成用+的，條件變為>= log(1.01)

[C++] 純文本查看 復制代碼

/*
    UVA 104
    AC
    56ms
*/


#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>




using namespace std;


int n;
double list[32][32][32];    //    [i][j][p] min dist of after
int through[32][32][32];
double target = 1.01;



void recover(int i, int j, int p)
{
    if(p==0)
        return;
    if(through[i][j][p] != -1)
        recover(i, through[i][j][p], p-1);
    printf("%d ",through[i][j][p]);
}

void SP()
{
    for(int p = 1 ; p <= n ; p++)
    {
        //update
        for(int k = 1 ; k <= n ; k++)
            for(int i = 1 ; i <= n ; i++)
                for(int j = 1 ; j <= n ; j++)
                    if(list[i][k][p-1]*list[k][j][0] > list[i][j][p])
                    {
                        list[i][j][p] = list[i][k][p-1]*list[k][j][0];
                        through[i][j][p] = k;
                    }
                        
                        
        //check
        for(int i = 1 ; i <= n ; i++)
        {
            if(list[i][i][p] >= target)
            {
                printf("%d ",i);
                recover(i,i,p);
                printf("%d\n",i);
                return;
            }
        }
    }
    
    puts("no arbitrage sequence exists");
    return;
}


int main()
{
    while(~scanf("%d",&n))
    {
        //init
        memset(list,0,sizeof(list));
        memset(through, -1, sizeof(through));
        
        //input
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                if(i!=j)
                    scanf("%lf", &list[i][j][0]);
                
        
        SP();
    }
    return 0;
}