ধরুন, আমাদের একটি ন্যূনতম সংযুক্ত গ্রাফ দেওয়া হয়েছে। তার মানে যেকোন প্রান্ত অপসারণ করলে গ্রাফটি সংযোগ বিচ্ছিন্ন হয়ে যাবে। গ্রাফটিতে n শীর্ষবিন্দু রয়েছে এবং প্রান্তগুলি একটি অ্যারে 'এজ'-এ দেওয়া হয়েছে। এছাড়াও আমাদের দেওয়া একটি অ্যারে 'vertexValues' রয়েছে যাতে n পূর্ণসংখ্যার মান রয়েছে।
এখন, আমরা নিম্নলিখিতগুলি করি -
-
আমরা প্রতিটি শীর্ষবিন্দুতে একটি ধনাত্মক পূর্ণসংখ্যা লিখি এবং তারপর একটি স্কোর গণনা করার চেষ্টা করি৷
-
দুটি শীর্ষবিন্দুকে সংযুক্ত করার জন্য একটি প্রান্ত রয়েছে, আমরা প্রান্তে দুটি শীর্ষবিন্দুর ছোট মান রাখি৷
-
আমরা সমস্ত প্রান্ত মান যোগ করে স্কোর গণনা করি।
আমাদের সর্বোচ্চ মান খুঁজে বের করতে হবে যা শীর্ষবিন্দুতে মান স্থাপন করে অর্জন করা যেতে পারে। আমাদের সর্বোচ্চ মোট মান এবং মানগুলি শীর্ষবিন্দুতে লিখতে হবে।
সুতরাং, যদি ইনপুট n =6 এর মত হয়, প্রান্ত ={{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, vertexValues ={1, 2, 3, 4, 5, 6}, তাহলে আউটপুট হবে 15, 3 1 2 4 5 6, কারণ আমরা প্রদত্ত উপায়ে 0 থেকে n – 1 পর্যন্ত শীর্ষবিন্দুতে মান রাখতে পারি 3 1 2 4 5 6 .
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
N := 100
Define arrays seq and res of size N.
Define an array tp of size N.
ans := 0
Define a function dfs(), this will take p, q,
res[p] := seq[c]
if p is not equal to 0, then:
ans := ans + seq[c]
(decrease c by 1)
for each value x in tp[p], do:
if x is not equal to q, then:
dfs(x, p)
for initialize i := 0, when i + 1 < n, update (increase i by 1), do:
tmp := first value of edges[i]- 1
temp := second value of edges[i] - 1
insert temp at the end of tp[tmp]
insert tmp at the end of tp[temp]
for initialize i := 0, when i < n, update (increase i by 1), do:
seq[i] := vertexValues[i]
c := n - 1
sort the array seq
dfs(0, 0)
print(ans)
for initialize i := n - 1, when i >= 0, update (decrease i by 1), do:
print(res[i]) উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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;
} ইনপুট
6, {{1, 2}, {2, 3}, {2, 4}, {4, 5}, {3, 6}}, {1, 2, 3, 4, 5, 6}
আউটপুট
15 3 1 2 4 5 6
