UVa10448 - Unique World(動態規劃)

題目大意

獨特世界裡面的人開車非常特別，他們從任意一個點出發到另外一個點的成本都是唯一無二的且只有一種走法，因此獨特世界只要看到成本就可以知道這是從 A 到 B 的車票，但獨特世界裡面突然發現了一個大問題，他們發現只要你願意繞路就可以讓任意一個點出發到另外一個點的成本竟然可以有多種解法，且成本不一致！
因此總統下令

• 每一條路徑可以重複走，只有終點與前一個點的路徑只能走一遍
• 不可以走非必要路徑
• 必須讓開車成本符合總統要求的成本

如果可以就輸出 yes、最小使用道路數量，no 表示不行
好了，現在需要一個程式設計師來解決問題了！
注意，每一個 test case 中間要有斷行

重點觀念

• 看得懂題目，這題題目也太難看懂了…
• 了解 DFS、動態規劃
• 了解題目細節
  題目非常多小機關，透過分析說明。

分析

• 噁心，太噁心了…，把兩題結合成一題，又有一堆細節要處理..
• 定義名詞
  • require_cost 政府要求的 cost
• 首先我們從題目中知道，每個節點都有一個獨特路徑。因此必須先走一次 DFS，找到最好的解法。並且判斷一些問題
  • 我們必須要確定 A 到 B 有連通
  • require_cost 要減掉所有經過路線的 cost
  • 紀錄所有路徑的成本
• DFS 後，我們接下來會發現一些問題
  • require_cost < 0，解不出來
  • require_cost == 0，完美，直接輸出 dfs 路徑的數量
  • 如果有 require_cost > 0 那怎麼辦?
    • 可以轉化成動態規劃，我們來判斷我們要重複走幾次必要路徑，才能讓 require_cost == 0
    • 概念如下：有 require_cost，我們最少用幾個 cost 讓 require_cost == 0
• 動態規劃，一樣有一些問題要注意
  • 必須先將 require_cost / 2，因為多走一步就必須在退回一步
  • 因此我們可以得知，當 dfs 後的 require_cost 為奇數時，一定是 no，因為每一個路徑走過去又走回來一定是 \(路徑 * 2\)，不可能會有奇數
  • 題目有說，終點與前一個點的路徑只能走一遍，因此我們要把終點與前一個點的 cost erase。
  • 紀錄當問題求最小時，必須讓 dp 初始化時都是 INF。
  • DFS 的路徑數量 == 成本數量

心得

天啊，這題太狠了….，這題目好多細節，DP 與 DFS 的融合，太可怕了…我學到好多東西。

老實講，這個其實還不賴，就是我在解決這題時思考的稍微有點久，也花了些時間先看懂別人如何寫的我再來自己試寫一遍。

然後那個 UVa 那個格式有時候真的很機車QQQ，不要這樣啦。
希望我到時候都能在寫其他題目時注意到這些細節

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
//#define int long long
#define MAXN 60
#define MAXN_cost 100020
#define INF 0x3f3f3f3f
using namespace std;
int t, n, m, q;
int id1, id2, cost;
int from, to, require_cost;
int visit[MAXN];
int dp[MAXN][MAXN_cost];
struct edge{
    int node, cost;
};
vector<edge> road[MAXN]; 
vector<int> travel_cost;


int dfs(int root){
    //cout << "root to " << root << ' ' << to << '\n';
    if(root == to) return 1; 
    if(visit[root]) return 0; //已被經過

    visit[root] = 1;
    for(int i = 0; i < road[root].size(); i++){ //不斷嘗試尋找可能路徑
        if(dfs(road[root][i].node)){
            require_cost -= road[root][i].cost;
            //注意邏輯，這裡是越後面的 path 會放在 vector 前面
            travel_cost.push_back(road[root][i].cost); 
            return 1;
        }
    }
    return 0;
}

int coin_change(){
    if(from == to) return -1; //UVa debug 有這個測資，但 UVa online judge 沒用
    //cout << "fron to require_cost " << from << ' ' << to << ' ' << require_cost << "\n";
    int connected = dfs(from); //判斷是否有唯一路徑
    //cout << "connected status " << connected << "\n";
    //cout << "required cost " << require_cost << "\n";

    //if(connected == 0) return -1; 題目有說，一定有唯一路徑，因此不用判斷
    if(require_cost == 0) return travel_cost.size(); //分析第 4-2 點
    if(require_cost < 0 || require_cost % 2 == 1) return -1; //分析第 4-1、5-2 點
    travel_cost.erase(travel_cost.begin()); //分析 5-2 點
    if(travel_cost.size() == 0) return -1; //如果沒有其他可重複路徑，但還有成本，那也解不出來

    //cout << "start dp " << '\n';
    //for(int i = 0; i < travel_cost.size(); i++) cout << travel_cost[i] << ' ';
    //cout << '\n';
    require_cost /= 2; //折半，走一步、退回一步
    dp[0][0] = 0; //dp 一開始初始化 dp[i][j], i = 使用的路徑、j = require_cost
    for(int i = 0; i < travel_cost.size(); i++){
        for(int j = 0; j <= require_cost; j++){
            if(j - travel_cost[i] >= 0) dp[i][j] = min(dp[i][j], dp[i][j - travel_cost[i]]+1);
            //if(j - travel_cost[i] >= 0) cout << j << " " << dp[i][j] << '\n';

            //狀態轉移
            if(i > 0) dp[i][j] = min(dp[i-1][j], dp[i][j]);
        }
    }

    //cout << "travel_cost.size()-1 " << travel_cost.size()-1 << '\n';
    //cout << dp[travel_cost.size()-1][require_cost] << ' ' << INF << '\n';

    //如果 requre_cost 有答案，就直接輸出，沒有就是 -1
    if(dp[travel_cost.size()-1][require_cost] == INF) return -1;
    //由於 dp 這邊是算來回走，
    //因此 DFS 路徑數量(路徑數量 == 成本數量) + dp * 2 + 終點與前一個點的路徑只能走一遍
    return travel_cost.size() + dp[travel_cost.size()-1][require_cost] * 2 + 1;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 0; i <= n; i++) road[i].clear(); //路徑清空
        //放入路徑，為了效率， road[i][j]，i 為 node、j 為 node 的第幾個路徑
        for(int i = 0; i < m; i++){ 
            cin >> id1 >> id2 >> cost;
            road[id1].push_back({id2, cost});
            road[id2].push_back({id1, cost});
        }

        cin >> q;
        for(int i = 0; i < q; i++){
            travel_cost.clear(); //紀錄成本的 vector 刪除
            memset(visit, 0, sizeof(visit)); //初始 visit
            memset(dp, INF, sizeof(dp)); //初始 dp

            cin >> from >> to >> require_cost;
            int ans = coin_change();
            if(ans == -1) cout << "No" << "\n";
            else cout << "Yes " << ans << "\n";
        }

        if(t != 0) cout << "\n"; //題目要求換行
    }

    return 0;
}