C ++で重みの観点から最も長いパスが最小化されるように、エッジに重みを割り当てます。

ここで1つの問題が発生します。この問題では、ツリーの1つのエッジと合計Sが与えられます。タスクは、重みの観点から最長のパスが最小化されるように、他のすべての重みに重みを割り当てることです。割り当てられた重みの合計は「S」と同じです。

アプローチは簡単です。パスに最大2つのリーフノードを含めることができるツリーのプロパティ。それは解決策を得るために使用されます。したがって、リーフノードを接続しているエッジのみに重みを割り当て、他のエッジを0に割り当てると、リーフノードに接続しているすべてのエッジが

パスには最大2つのリーフノードを含めることができるため、最長のパスは次のようになります

例

#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