資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚科學
法律科學用 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
更新於：2019-08-20
102 次瀏覽
廣告