โปรแกรม C++ หาผลรวมสูงสุดของกราฟเชื่อมต่อขั้นต่ำด้วยค่าจุดยอด

กราฟเชื่อมต่อขั้นต่ำ (Minimally connected = ต้นไม้) n จุดยอด มี vertexValues n ค่า ใส่ค่าเหล่านี้ลงจุดยอด (เรียงลำดับอย่างใดอย่างหนึ่ง) ขอบแต่ละเส้นได้ค่า = min(ค่าสองปลาย) ผลรวมขอบ = คะแนน ต้องการคะแนนสูงสุด และการจัดค่าที่ให้คะแนนนั้น

ตัวอย่าง: n=6, edges={{1,2},{2,3},{2,4},{4,5},{3,6}}, vertexValues={1,2,3,4,5,6} ผลลัพธ์: 15, 3 1 2 4 5 6

ขั้นตอนการแก้ปัญหา (DFS + Greedy Assign)

1. สร้างกราฟจาก edges
2. เรียง vertexValues น้อยไปมาก
3. DFS จากราก (0) ใหม่ค่าจาก seq เริ่มจากค่ามากสุด (c = n-1 ลดลงเรื่อยๆ):
   • res[p] = seq[c] ถ้า p != 0 บวก seq[c] เข้า ans
   • c-- แล้ว DFS ลูกต่อ
4. ค่าที่มากที่สุดจะอยู่ที่ราก (ไม่ถูกนับในผลรวมขอบ) ค่าต่อไปจะกระจายให้ขอบได้ค่ามากที่สุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

#define N 100
int seq[N], res[N];
vector<int> tp[N];
int ans = 0, c;

void dfs(int p, int q) {
    res[p] = seq[c];
    if (p != 0) ans += seq[c];
    c--;
    for (auto x : tp[p])
        if (x != q) dfs(x, p);
}

void solve(int n, vector<pair<int,int>> edges, int vertexValues[]) {
    for (int i = 0; i+1 < n; i++) {
        int tmp = edges[i].first - 1;
        int temp = edges[i].second - 1;
        tp[tmp].push_back(temp);
        tp[temp].push_back(tmp);
    }
    for (int i = 0; i < n; i++) seq[i] = vertexValues[i];
    c = n - 1;
    sort(seq, seq + n);
    dfs(0, 0);
    cout << ans << endl;
    for (int i = n-1; i >= 0; i--) cout << res[i] << " ";
    cout << endl;
}

int main() {
    int n = 6;
    vector<pair<int,int>> edges = {{1,2},{2,3},{2,4},{4,5},{3,6}};
    int vertexValues[] = {1,2,3,4,5,6};
    solve(n, edges, vertexValues);
    return 0;
}

อินพุต / เอาต์พุต

Input: 6, {{1,2},{2,3},{2,4},{4,5},{3,6}}, {1,2,3,4,5,6}

Output: 15 3 1 2 4 5 6