假设有一个加权无向图，它有n个顶点和m条边。图的得分定义为图中所有边权重的总和。边权重可以是负数，如果移除它们，图的得分将增加。我们需要做的是，在保持图连通的同时，通过移除图中的边来使得图的得分最小化。我们需要找出可以减少的最大得分。
图以数组’edges’的形式给出，其中每个元素的形式为{weight, {vertex1, vertex2}}。
因此，如果输入为n = 5，m = 6，edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}，则输出将为4。
如果我们从图中移除边(1, 2)和(2, 5)，得分的总减少量将为4，且图仍然保持连通。
立即学习“C++免费学习笔记（深入）”；
为了解决这个问题，我们将按照以下步骤进行：
cnum := 0Define an array par of size: 100.Define an array dim of size: 100.Define a function make(), this will take v, par[v] := v dim[v] := 1Define a function find(), this will take v, if par[v] is same as v, then: return v return par[v] = find(par[v])Define a function unify(), this will take a, b,a := find(a)b := find(b)if a is not equal to b, then: (decrease cnum by 1) if dim[a] > dim[b], then: swap values of (a, b) par[a] := b dim[b] := dim[b] + dim[a]cnum := nsort the array edges based on edge weightsfor initialize i := 1, when i = 0, then: res := res + 1 * weight Ignore following part, skip to the next iteration if cnum is same as 1, then: if weight >= 0, then: res := res + 1 * weight Otherwise unify(a, b)return res
登录后复制
示例
让我们看看以下实现，以便更好地理解 –
#include using namespace std;int cnum = 0;int par[100];int dim[100];void make(int v){ par[v] = v; dim[v] = 1;}int find(int v){ if(par[v] == v) return v; return par[v] = find(par[v]);}void unify(int a, int b){ a = find(a); b = find(b); if(a != b){ cnum--; if(dim[a] > dim[b]){ swap(a, b); } par[a] = b; dim[b] += dim[a]; }}int solve(int n, int m, vector >> edges){ cnum = n; sort(edges.begin(), edges.end()); for(int i = 1; i = 0) res += 1 * weight; continue; } if(cnum == 1){ if(weight >= 0) res += 1 * weight; } else{ unify(a, b); } } return res;}int main() { int n = 5, m = 6; vector >> edges = {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}; cout输入
5, 6, {{2, {1, 2}}, {2, {1, 3}}, {1, {2, 3}}, {3, {2, 4}}, {2, {2, 5}}, {1, {3, 5}}}
登录后复制
输出
4
登录后复制
以上就是C++程序用于找出可以从图中减少的最大得分量的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583359.html
