UVa12862 - Intrepid climber(DFS)

題目大意

你爬上了山峰！你想把這個興奮的心情告訴其他還在爬山朋友，但那些朋友都還在山上爬，你要跑下去跟他們說。
現在你想要跟全部的朋友講，下山不需要花很多體力、但是上山需要花體力，但是題目保證一定會有一條完整的路徑(不會經過重複的路)可以讓你可以走到每個朋友的身邊。

現在請你算出你走到每個朋友身邊需要耗費多少體力。
題目連結

重點觀念

• 了解 DFS
• 認識尤拉路徑
• 發現題目的細節

分析

• 我們可以觀察題目，發現一個很有趣的事情
• 因為題目保證我們只會有一條路徑！因此我們不需要找出路徑
• 只要找到最後一個朋友，就不需要在移動
• 所以我們只要找出所有的路徑，找到有一條從山峰到路徑累積 weights 最大，並把它當作最後一條路徑，然後扣掉他(因為找到最後一個朋友，不需要再移動)。
• 為甚麼是從山峰到路徑累積 weights 最大則是因為
  • 山峰是最高點
  • 我們可以把她想像成有兩種路徑以山峰為起點，一種是從左邊下山遇到朋友、另一種則是從右邊下山遇到朋友。
    註：山峰並不代表一開始的題目位置，題目只有說有唯一路徑，並沒有說都會經過題目初始位置
  • 因此我們可以把題目轉化成，從左邊下山後上山 or 從右邊下山後上山，哪邊花的能量比較少，就選那邊下山後上山，再去找另一邊的朋友，然後就下山，不需要再耗費能量。

參考連結

Uva12862 - Intrepid climber By txya900619
UVa 12862 - Intrepid climber By Morris

心得

這題完全考細節，不考程式碼難度，太秀了。希望我以後也可以發現這些邏輯

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 100020
using namespace std;
int f, n;
vector<pair<int, int> > nodes[MAXN]; //題目的邊 first 2nd node, second weights
int pal[MAXN]; //朋友[i] = 1，表示是不是有 i 這個朋友
int a, b, c, l;
int max_weights, ans;//max_weights 最長的一個邊， ans 答案

int dfs(int root, int weights){
    int visited_friend = 0; //遇過了幾個朋友
    if(pal[root] == 1){ //發現朋友
        max_weights = max(weights, max_weights); 
        visited_friend++;
    }

    for(int i = 0; i < nodes[root].size(); i++){ //不斷找朋友
        int node = nodes[root][i].first, weight = nodes[root][i].second;
        int visit_friend = dfs(node, weights+weight);//往這邊走有幾個朋友
        visited_friend += visit_friend; //紀錄遇到幾個朋友了
        if(visit_friend) ans += weight; //如果有找到朋友，表示這路徑要加近來
    }

    //cout << "root visit_friend " << root << " " << visited_friend << "\n";
    return visited_friend;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> f >> n){
        for(int i = 0; i <= f; i++) nodes[i].clear(); //清除資料
        for(int i = 0; i < f-1; i++){ //輸入資料
            cin >> a >> b >> c;
            nodes[a].push_back(make_pair(b, c));
        }

        memset(pal, 0, sizeof(pal)); //清除朋友資訊
        for(int i = 0; i < n; i++){ //輸入朋友位置
            cin >> l;
            //cout << "l " << l << "\n";
            pal[l] = 1;

        }
        max_weights = 0, ans = 0; 
        dfs(1,0);
        //cout << "ans " << ans << "\n";
        cout << ans - max_weights << "\n"; //減掉最大的

    }
    return 0;
}