题目大意
\(\qquad\)给定一张无向图,没有重边和自环,要删去一些边但是仍然要保证图的连通性,求这些边边权总和的最大值。
解题思路
\(\qquad\)我们不一定要真的去统计它的最大值,因为所有边的权值总和是不变的,所以我们算出来保留的边的权值总和越小,删掉的边的权值总和越大。
\(\qquad\)如果是统计保留的边,那保证连通性就简单多了,我们可以用到最小生成树,这里采用Kruskal
算法,因为好写
,Kruskal
要用到并查集,别忘记初始化
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 11000, M = 22000;
int p[N], n, m;
struct Edge {
int u, v, w;
bool operator <(const Edge& W) const {
return w < W.w;
}
} edge[N];
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int Krus()
{
sort(edge + 1, edge + 1 + m);
int res = 0;
for (int i = 1; i <= m; i ++ )
{
int fu = find(edge[i].u), fv = find(edge[i].v);
if (fu == fv) continue ;
else {
p[fu] = fv;
res += edge[i].w;
}
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
int sum = 0;
for (int i = 1; i <= m; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w}, p[i] = i;
sum += w;
}
printf("%d\n", sum - Krus());
return 0;
}