列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[sagit]

NPSC 2008 高中組 決賽 C.咒語

說明：給你一個邊有權重的無向圖，請你找出一條從起點走到終點權重最大的路徑，中間經過的點的編號必須依照順序，也就是說從1走到n，中間某些點可以跳過不走，但順序一定是編號小的在前面。

解法：動態規劃(DP)解，我們可以設一個陣列 Ans[] 記錄走到該點的最大權重，當我們只考慮 k 點的前一個點的編號，則可以得到： Ans[k] 的值為 Ans[j]+W[j][k] (0<=j<k) 的最大值，其中 W[j][k] 代表從 j 點到 k 點這條邊的權重。為了加快處理速度，我們只處理權重大於 0 的邊，因為 Ans[] 的值是遞增的，所以邊的權重為 0 的情況其最大值為 Ans[k-1]，只要處理這個就行了。

參考程式：(By sagit)

代碼: [選擇]

// NPSC 2008 高中組決賽
// 題目 C - 咒語
// By sagit at TCGS
#include <cstdlib>
#include <iostream>
#include <deque>

using namespace std;

const int MAX=10001;
deque<int> Y[MAX], Z[MAX];              // Y 記錄前一個點, Z 記錄該通道人數
int Ans[MAX];                           // 記錄到該點為止可以遇到的最大人數

int main()
{
    freopen("pc.in", "rt", stdin);
    freopen("pc.out", "w+t", stdout);
    ios_base::sync_with_stdio(false);
    int n, m, i, j, x, y, z, t;
    while (1)
    {
        cin >> n >> m;
        if ( n==0 && m==0 ) break;
        for (i=0; i<n; i++)             // 啟始化
        {
            Y[i].clear();
            Z[i].clear();
        }
        for (i=0; i<m; i++)             // 記錄前一個點到該點可遇到的人數
        {
            cin >> x >> y >> z;
            if ( x<y ) { t=x; x=y; y=t; }
            Y[x].push_back(y);
            Z[x].push_back(z);
        }
        for (i=1, Ans[0]=0; i<n; i++)   // 尋找以 j 為中間點可遇到的最大人數
        {
            for (j=0, z=Ans[i-1]; j<Y[i].size(); j++)
            {
                x=Ans[Y[i][j]]+Z[i][j];
                if (x>z) z=x;
            }
            Ans[i]=z;
        }
        cout << Ans[n-1] << endl;
    }
//    system("PAUSE");
    return 0;
}

[lini]

題目寫錯了 ..

(1) a1=0, ak=n

應該是 n-1