मान लीजिए एक न्यूनतम संबद्ध ग्राफ दिया गया है। इसका अर्थ है कि किसी भी एज को हटाने से ग्राफ असंबद्ध हो जाएगा। ग्राफ में n वर्टेक्स हैं और एज 'edges' सरणी में दी गई हैं। एक सरणी 'vertexValues' भी दी गई है जिसमें n पूर्णांक मान हैं।
अब हम निम्न करते हैं:
- प्रत्येक वर्टेक्स पर एक धनात्मक पूर्णांक लिखते हैं और फिर स्कोर की गणना करने का प्रयास करते हैं।
- दो वर्टेक्स को जोड़ने वाली एज होती है, हम दोनों वर्टेक्स के मानों में से छोटे मान को एज पर रखते हैं।
- सभी एज मानों को जोड़कर स्कोर की गणना करते हैं।
हमें वर्टेक्स पर मान रखकर प्राप्त किए जा सकने वाले अधिकतम मान की गणना करनी है। हमें अधिकतम कुल मान और वर्टेक्स पर लिखे जाने वाले मान प्रिंट करने हैं।
उदाहरण के लिए, यदि इनपुट है 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 होगा, क्योंकि हम वर्टेक्स पर मान 0 से n-1 तक दिए गए तरीके 3 1 2 4 5 6 में रख सकते हैं।
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
N := 100
आकार N के सरणी seq, res परिभाषित करें
आकार N का सरणी tp परिभाषित करें
ans := 0
एक फंक्शन dfs() परिभाषित करें जो p, q लेता है:
res[p] := seq[c]
यदि p != 0, तो:
ans := ans + seq[c]
c घटाएँ
tp[p] में प्रत्येक मान x के लिए:
यदि x != q, तो:
dfs(x, p)
i := 0 से n-2 तक:
tmp := edges[i] का पहला मान - 1
temp := edges[i] का दूसरा मान - 1
temp को tp[tmp] के अंत में डालें
tmp को tp[temp] के अंत में डालें
i := 0 से n-1 तक:
seq[i] := vertexValues[i]
c := n - 1
seq सरणी को सॉर्ट करें
dfs(0, 0)
ans प्रिंट करें
i := n-1 से 0 तक घटाते हुए:
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
