数据结构
网络
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 次浏览
广告