यहां हम एक समस्या देखेंगे, इस समस्या में एक ट्री का एक एज और एक योग S दिया गया है। कार्य अन्य सभी वेट्स को वेट असाइन करना है, ताकि वेट के संदर्भ में सबसे लंबा पथ न्यूनतम हो। असाइन किए गए वेट्स का योग 'S' के समान है।
दृष्टिकोण सरल है। एक ट्री की संपत्ति कि एक पथ में अधिकतम दो लीफ नोड्स हो सकते हैं। इसका उपयोग समाधान प्राप्त करने के लिए किया जाएगा। इसलिए यदि हम केवल लीफ नोड्स से जुड़े एज को वेट असाइन करते हैं, और अन्य एज को 0 असाइन करते हैं। तो प्रत्येक एज जो लीफ नोड्स से जुड़ा है, उसे असाइन किया जाएगा:
चूंकि एक पथ में अधिकतम दो लीफ नोड्स हो सकते हैं, इसलिए सबसे लंबा पथ होगा:
उदाहरण
#include<iostream> #include<vector> using namespace std; void insertEdge(int u, int v, vector<int> adj[]) { adj[u].push_back(v); adj[v].push_back(u); } long double pathLength(vector<int> adj[], int sum, int n) { int count = 0; for (int i = 1; i <= n; i++) { if (adj[i].size() == 1) count++; } long double ans = 2.0 * (long double)(sum / (long double)(count)); return ans; } int main() { int n = 6; vector<int> adj[n + 1]; insertEdge(1, 2, adj); insertEdge(2, 3, adj); insertEdge(2, 4, adj); insertEdge(4, 5, adj); insertEdge(4, 6, adj); int sum = 1; cout << pathLength(adj, sum, n); } आउटपुट
0.5
