C++-এ ন্যূনতম সংযুক্ত গ্রাফের সর্বাধিক এজ ভ্যালু বের করুন

একটি ন্যূনতম সংযুক্ত গ্রাফ (minimally connected graph) দেওয়া আছে — অর্থাৎ যেকোনো এজ মুলে গ্রাফ ডিসকানেক্টেড হয়ে যাবে। গ্রাফে n ভেরটেক্স আছে এবং এজগুলো edges অ্যারে দিয়ে দেওয়া আছে। প্রতিটি ভেরটেক্সের জন্য একটি মান দেওয়া আছে vertexValues অ্যারেতে।

নিম্নলিখিত নিয়মে স্কোর বের করতে হবে:

1. প্রতিটি ভেরটেক্সে একটি ধনাত্মক পূর্ণসংখ্যা লিখুন।
2. যে এজ দুটি ভেরটেক্স সংযুক্ত করে, সেটির মান হবে দুই ভেরটেক্সের মানের ন্যূনতম।
3. সকল এজের মানের যোগফল হচ্ছে টোটাল স্কোর।

লক্ষ্য: ভেরটেক্সগুলোতে মান বসিয়ে সর্বাধিক সম্ভাব্য স্কোর বের করুন এবং সেই মানগুলোও প্রিন্ট করুন।

উদাহরণ

ইনপুট: 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)

1. ভেরটেক্স মানগুলো সর্ট করুন (সর্বনিম্ন থেকে সর্বোচ্চ)।
2. রুট (০) থেকে DFS শুরু করুন।
3. প্রতিটি নোডে বর্তমান সবচেয়ে বড় উপলব্ধ মান বসান।
4. রুট ছাড়া প্রতিটি নোডের জন্য, সেই নোডের মান টোটাল স্কোরে যোগ হয় (কারণ এজের মান = ন্যূনতম(প্যারেন্ট, চাইল্ড) = চাইল্ড মান, কারণ চাইল্ড মান প্যারেন্টের চেয়ে ছোট হবে)।
5. এভাবে সর্বোচ্চ মানগুলো লিফ নোডগুলোতে বসে, যা টোটাল স্কোর বেড়ায়।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#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;
}

আউটপুট

15
3 1 2 4 5 6

ব্যাখ্যা

• সর্ট করা মান: 1,2,3,4,5,6।
• DFS ট্রি-ট্রাভার্সালে সবচেয়ে বড় মান (৬) রুটে যায়, কিন্তু রুটের মান স্কোরে যোগ হয় না।
• পরবর্তী বড় মানগুলো (৫,৪,৩,২,১) চাইল্ড নোডগুলোতে যায়, এজ ভ্যালু বেড়ায়।
• ফলাফলস্বরূপ ম্যাক্সিমাম স্কোর ১৫।