मान लीजिए, हमें एक न्यूनतम जुड़ा हुआ ग्राफ दिया गया है। इसका मतलब है कि किसी भी किनारे को हटाने से ग्राफ डिस्कनेक्ट हो जाएगा। ग्राफ में 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