C++에서 가중치 측면에서 가장 긴 경로가 최소화되도록 모서리에 가중치를 할당합니다.

여기에서 우리는 한 가지 문제를 볼 것입니다. 이 문제에서 트리의 한 모서리와 합 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