यहाँ हम एक समस्या देखेंगे, इस समस्या में एक पेड़ का एक किनारा और एक योग 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