Bài toán: cho một cây và tổng S. Gán trọng số cho các cạnh sao cho đường đi dài nhất theo trọng số được tối thiểu. Tổng trọng số gán bằng S.
Cách tiếp cận: tính chất của cây – một đường đi có tối đa 2 nút lá. Gán trọng số chỉ cho cạnh nối nút lá, các cạnh khác gán 0. Mỗi cạnh nối nút lá được gán:
Vì đường đi chứa tối đa 2 nút lá, đường đi dài nhất sẽ là:
Ví dụ mã C++
#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);
} Kết quả
0.5