定树T = (V,E),如果每个顶点都有一个权重,比如利益,使用C++贪心算法来获得最大的利益,如果一个顶点已经被选中,那么它的相邻顶点不能被选中。
时间: 2023-12-13 15:05:16 浏览: 25
树的最大权值独立集问题可以用贪心算法来解决。在每次选择节点时,选择当前节点和其子节点的子树中未被选择的节点中权值最大的节点加入到集合中。这个算法的正确性基于树的贪心选择性质。具体实现步骤如下:
1. 将所有节点按照权值从大到小排序。
2. 从权值最大的节点开始,依次考虑每个节点。
3. 对于每个节点,如果其相邻的节点已经被选中,则不能选择该节点,否则将该节点加入到集合中。
4. 更新相邻节点是否被选中的状态。
5. 重复步骤2-4,直到所有节点都被考虑过。
C++代码如下:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10010;
struct Node {
int id;
int w;
bool operator < (const Node& a) const {
return w > a.w;
}
};
vector<Node> G[MAXN];
bool vis[MAXN];
int ans = 0;
void dfs(int u, int fa) {
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i].id, w = G[u][i].w;
if (v == fa) continue;
dfs(v, u);
if (!vis[v]) ans += w;
else vis[u] = true;
}
}
int main() {
int n, u, v, w;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w;
G[i].push_back({i, w});
}
for (int i = 1; i < n; i++) {
cin >> u >> v;
G[u].push_back({v, G[v][0].w});
G[v].push_back({u, G[u][0].w});
}
sort(G + 1, G + n + 1);
for (int i = 1; i <= n; i++) {
int u = G[i][0].id;
bool flag = true;
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].id;
if (vis[v]) {
flag = false;
break;
}
}
if (flag) {
vis[u] = true;
ans += G[i][0].w;
for (int j = 0; j < G[u].size(); j++) {
int v = G[u][j].id;
vis[v] = true;
}
}
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
```
其中,vis[u]表示节点u是否被选中,ans表示最大的利益。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)