当前位置： 首页 > ds >正文

【贪心 逆向思考 并集查找 数学归纳法】P7162 [COCI 2020/2021 #2] Sjekira|普及+

ds 2025/8/27 5:13:03

本文涉及知识点

C++贪心
C++图论
C++并集查找 预计2025年5月29号 7:00发布

P7162 [COCI 2020/2021 #2] Sjekira

题目描述

有一棵 n n n 个结点的树，每个结点有一个权值，删除一条边的费用为该边连接子树中结点权值最大值之和。问以任意顺序删除树中所有边的最小花费。

输入格式

第一行一个整数 n n n，表示结点数。
第二行 n n n 个整数 t 1 , t 2 , … , t n t_1, t_2, \ldots , t_n t1​,t2​,…,tn​，其中第 i i i 个数表示结点 i i i 的权值。
接下来 n − 1 n-1 n−1 行，每行两个整数 x , y x, y x,y，表示 x x x 和 y y y 之间有一条边。

输出格式

输出一个数，代表最小花费。

输入输出样例 #1

输入 #1

3
1 2 3
1 2
2 3

输出 #1

8

输入输出样例 #2

输入 #2

4
2 2 3 2
1 3
3 2
4 3

输出 #2

15

输入输出样例 #3

输入 #3

5
5 2 3 1 4
2 1
3 1
2 4
2 5

输出 #3

26

说明/提示

【样例解释 #1】

先删 ( 2 , 3 ) (2,3) (2,3)，再删 ( 1 , 2 ) (1,2) (1,2)，花费为 5 + 3 = 8 5+3=8 5+3=8。

【数据范围】

对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 100 , 000 1 \leq n \leq 100,000 1≤n≤100,000， 1 ≤ t i ≤ 10 9 1 \leq t_i \leq 10^9 1≤ti​≤109。

Subtask #1（ 10 10 10 pts）： n ≤ 10 n \leq 10 n≤10。
Subtask #2（ 10 10 10 pts）： i i i 与 i − 1 i-1 i−1 有边直接相连。
Subtask #3（ 30 30 30 pts）： n ≤ 1000 n \leq 1000 n≤1000。
Subtask #4（ 50 50 50 pts）：无附加限制。

【说明】

译自 Croatian Open Competition in Informatics 2020 ~ 2021 Round 2 D Sjekira。

贪心 逆向思考 并集查找

权值w1最大的节点有n1条边，则w1至少贡献n1次。权值w的节点有n条边，则w及更大的权值至少贡献n次。故先从权值大的节点删除。
任意边，我们令权值大的为起点，权值小的位终点。先删除起点权重大的。起点权值相同，删除终点权值大的。我们逆序操作，用这些边把这些点连接起来。
先连起点权值小，起点权重相同连终点权值小的。用并集查找 记录各连通区域（子树）的节点，用变量vMax记录各连通区域的最大值。
vMax和ans用long long表示。

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}class CUnionFind
{
public:CUnionFind(int iSize) :m_vNodeToRegion(iSize){for (int i = 0; i < iSize; i++){m_vNodeToRegion[i] = i;}m_iConnetRegionCount = iSize;}CUnionFind(vector<vector<int>>& vNeiBo) :CUnionFind(vNeiBo.size()){for (int i = 0; i < vNeiBo.size(); i++) {for (const auto& n : vNeiBo[i]) {Union(i, n);}}}int GetConnectRegionIndex(int iNode){int& iConnectNO = m_vNodeToRegion[iNode];if (iNode == iConnectNO){return iNode;}return iConnectNO = GetConnectRegionIndex(iConnectNO);}void Union(int iNode1, int iNode2){const int iConnectNO1 = GetConnectRegionIndex(iNode1);const int iConnectNO2 = GetConnectRegionIndex(iNode2);if (iConnectNO1 == iConnectNO2){return;}m_iConnetRegionCount--;if (iConnectNO1 > iConnectNO2){UnionConnect(iConnectNO1, iConnectNO2);}else{UnionConnect(iConnectNO2, iConnectNO1);}}bool IsConnect(int iNode1, int iNode2){return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);}int GetConnetRegionCount()const{return m_iConnetRegionCount;}vector<int> GetNodeCountOfRegion()//各联通区域的节点数量{const int iNodeSize = m_vNodeToRegion.size();vector<int> vRet(iNodeSize);for (int i = 0; i < iNodeSize; i++){vRet[GetConnectRegionIndex(i)]++;}return vRet;}std::unordered_map<int, vector<int>> GetNodeOfRegion(){std::unordered_map<int, vector<int>> ret;const int iNodeSize = m_vNodeToRegion.size();for (int i = 0; i < iNodeSize; i++){ret[GetConnectRegionIndex(i)].emplace_back(i);}return ret;}
private:void UnionConnect(int iFrom, int iTo){m_vNodeToRegion[iFrom] = iTo;}vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引int m_iConnetRegionCount;
};
class Solution {
public:long long Ans(vector<int>& a, vector<pair<int, int>>& edge) {const int N = a.size();for (auto& [u, v] : edge) {u--, v--;if (a[u] < a[v]) { swap(u, v); }}vector<int>inx(N);sort(edge.begin(), edge.end(), [&](const pair<int, int>& pr1, const pair<int, int>& pr2) {return make_pair(a[pr1.first], a[pr1.second]) < make_pair(a[pr2.first], a[pr2.second]); });vector<int> vMax = a;CUnionFind uf(N);long long ans = 0;for (const auto& [u, v] : edge) {const int m1 = vMax[uf.GetConnectRegionIndex(u)];const int m2 = vMax[uf.GetConnectRegionIndex(v)];ans += m1 + m2;uf.Union(u, v);vMax[uf.GetConnectRegionIndex(u)] = max(m1, m2);}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);int n;cin >> n ;auto a = Read<int>(n);auto edge = Read<pair<int, int>>(n - 1);
#ifdef _DEBUG		//printf("N=%d",n);Out(a, "a=");Out(edge, ",edge=");//Out(que, ",que=");/*Out(que, "que=");*/
#endif // DEBUG		auto res = Solution().Ans(a,edge);	cout << res << "\n";return 0;
}

单元测试

vector<int> a;vector<pair<int, int>> edge;TEST_METHOD(TestMethod1){a = { 1,2,3 }, edge = { {1,2},{2,3} };auto res = Solution().Ans(a, edge);AssertEx(8LL, res);}TEST_METHOD(TestMethod2){a = { 2,2,3,2 }, edge = { {1,3},{3,2},{4,3} };auto res = Solution().Ans(a, edge);AssertEx(15LL, res);}TEST_METHOD(TestMethod3){a = { 5,2,3,1,4 }, edge = { {2,1},{3,1},{2,4},{2,5} };auto res = Solution().Ans(a, edge);AssertEx(26LL, res);}

贪心+数学归纳法

结果= 除最大点权外的点权之和(第一部分) + 各边最大点权。下面用数学归纳法来证明:
初始树调整成最大点权为根，子树一产生马上调整成最大点权为根。
层次为2的子树，显然符合。如果层次i的子树符合，则层次i+1的子树T也一定符合。
断开T和孩子的边，增加的成本：
a,子树的最大点权。
b，这些边的最大点权。
a和子树的第一部分相加后，就是T除根节点外的，所有子权和。
b和子树的第二部分相加后，就是所有边的最大点权和。
得到证明。

代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}class Solution {
public:long long Ans(vector<int>& a, vector<pair<int, int>>& edge) {const int N = a.size();for (auto& [u, v] : edge) {u--, v--;}long long ans = accumulate(a.begin(), a.end(), 0LL) - *max_element(a.begin(), a.end());for (const auto& [u, v] : edge) {ans += max(a[u], a[v]);}return ans;}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);int n;cin >> n ;auto a = Read<int>(n);auto edge = Read<pair<int, int>>(n - 1);
#ifdef _DEBUG		//printf("N=%d",n);Out(a, "a=");Out(edge, ",edge=");//Out(que, ",que=");/*Out(que, "que=");*/
#endif // DEBUG		auto res = Solution().Ans(a,edge);	cout << res << "\n";return 0;
}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

http://www.xdnf.cn/news/9515.html

相关文章：

  • 【RP2350】香瓜树莓派RP2350之USB HID
  • 《P1763 埃及分数》
  • Acrobat Reader 无法在 Windows 11及10 中打开的5种修复方法
  • 数据库表添加索引
  • STM32 Modbus RTU从机开发实战：核心实现与五大调试陷阱解析
  • 什么是Windows内存压缩? win10/11系统启用和禁用内存压缩的教程
  • HTB-Puppy
  • DAY 38 Dataset和Dataloader类
  • Linux网络编程（一）
  • 医疗影像检测系统设计与实现
  • open3d保存为pcl可以读取的ply点云
  • Windows 子系统 WSL 中宝塔安装 supervisor 启动失败解决方案
  • 《计算机组成原理》第 1 章 - 计算机系统概论
  • 工控安全审计与网络流量监控系统的协同防御
  • ‌CDGP|企业数据治理：莫让“打补丁”成为常态
  • STL容器使用中的常见问题解析
  • 辛格迪客户案例 | 博福-益普生实施YonSuite，同步开展计算机化系统验证(CSV)
  • Druid连接池使用和源码分析
  • 为Windows用户量身定制的监控方案
  • 通过 API 获取 1688 平台订单接口的技术实现
  • LeetCode 118 题解--杨辉三角
  • 软考 系统架构设计师系列知识点之杂项集萃（77）
  • 1435系列信号发生器
  • 2025年上半年软考系统架构设计师--案例分析试题与答案
  • pyｔｈｏｎ 生成复杂表格，自动分页等功能
  • 自动驾驶规划控制教程——不确定环境下的决策规划
  • 火柴INIBOX矿机实测850M算力即将改写Initverse挖矿规则
  • 模型可信度
  • 缩量资金迁徙下的短期博弈
  • phpstudy(1) -- 记录