题解 洛谷 P2700 【逐个击破】
2022/9/10 6:23:13
本文主要是介绍题解 洛谷 P2700 【逐个击破】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
\(P2700\) 逐个击破
前置知识
克鲁斯卡尔最小生成树算法 并查集 贪心思想
题目描述
给出一颗带权的树,删除任意条边,求出使得给定的点不连通的最小权值。
解题思路
样例说明:删除权值为\(1\)和\(3\)的边,使得\(1.2.4\)三点不连通,答案为\(1 + 3 = 4\)。
使删除的边总权值最小可以转化为使添加的边总权值最大。
借鉴克鲁斯卡尔算法的基本思想:贪心地选取当前未被选过的权值最大的边,将其建入图内,直至所有的非指定点都被并入图内。
统计出加入的边的权值,答案即为总边权 - 统计出的边权。
注意事项
1.按边权从大到小排序。
2.数据范围大,用 \(long long\) 存变量。
#include <bits/stdc++.h> #define re register #define il inline #define ll long long #define MAXN 100005 #define MAXM 100005 #define rep(i,a,b) for(re int i = a;i <= b;++ i) #define Rep(i,a,b) for(re int i = a;i < b;++ i) #define drep(i,a,b) for(re int i = a;i >= b;-- i) #define fin(a) freopen(#a".in","r",stdin) #define fout(a) freopen(#a".out","w",stdout) using namespace std; struct edge{ int u,v,w; }e[MAXM]; int n,k; int fa[MAXN]; bool p[MAXN]; ll ans = 0; il bool cmp(edge a,edge b){ return a.w > b.w; } il int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); } il void kruskal(){ Rep(i,1,n){ int u = e[i].u,v = e[i].v,w = e[i].w; int fu = find(u),fv = find(v); if(p[fu] && p[fv]) continue; fa[fu] = fv; ans -= w; if(p[fu]) p[fv] = 1; else if(p[fv]) p[fu] = 1; } } int main(){ #ifndef ONLINE_JUDGE fin(2700); fout(2700); #endif scanf("%d%d",&n,&k); rep(i,1,n) fa[i] = i; rep(i,1,k){ int point; scanf("%d",&point); p[point] = 1; } Rep(i,1,n){ scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); ans += e[i].w; } sort(e + 1,e + n + 1,cmp); kruskal(); printf("%lld",ans); return 0; }
这篇关于题解 洛谷 P2700 【逐个击破】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding