ที่นี่เราจะเห็นปัญหาหนึ่ง ในปัญหานี้ ให้ขอบต้นไม้หนึ่งต้นและให้ผลรวม 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
