当前位置: 首页 > news >正文

CF1508C tj

CF1508C

你总不能一下午啥事情都没干吧。

题面

作为一名教师,Riko Hakozaki 经常需要帮助她的学生解决各类学科的问题。今天,她被问到了一个编程任务,内容如下:

给定一个无向完全图,包含 \(n\) 个节点,其中部分边已经被赋予了正权值,其余边尚未赋值。你需要为所有未赋值的边分配非负权值,使得最终所有边都被赋值后的完全图中,所有边权的异或和等于 \(0\)

定义一个完全赋值的完全图的“丑陋度”为其最小生成树的权值,即最小生成树所有边权之和。你需要合理分配权值,使得最终图的丑陋度尽可能小。

提示:一个无向完全图有 \(n\) 个节点,包含所有 \(1 \le u < v \le n\) 的边;这样的图共有 \(\frac{n(n-1)}{2}\) 条边。

她不确定如何解决这个问题,因此请你帮她解决。

sol

又是分讨题。

设原来边权的异或值为 \(S\)

发现如果我们想要让这个最小生成树尽量小的话,有一个简单的做法是只定一条边为 \(S\),剩下全填 \(0\),感性理解一下会发现这个是对的。

在未赋值的边联通且有环的情况下答案一定为 \(0\)

接下来就有两种情况需要讨论了:

补图刚好是一棵树。

这种情况点数不会太多,暴力枚举哪条边改为 \(S\) 跑最小生成树就行了。

直接做就是 \(O(n^3\log n^2)\) 的。

补图不连通

这个时候也得分两种情况,看有没有环。

有环我直接把补图连通块跑出来搞最小生成树就行了,那个边权为 \(S\) 的边随便找个环放了就好了。

没环的时候也可以说明点数不会太多,也是枚举哪条边放就完事了,也是 \(O(n^3\log n^2)\)

代码还没写,但是这个能难写到哪去???

http://www.hskmm.com/?act=detail&tid=36737

相关文章:

  • 2025 年选客服系统必看:为什么头部企业都在用这几款客服系统?
  • 2025无氧干燥设备选购必看!覆盖真空/洁净/高温烘箱,三家靠谱厂家大盘点
  • 直流电机生产线厂家口碑榜:TOP3企业综合实力全景解析
  • Elasticsearch 快照同机 异机备份到 MinIO(Java 实现)
  • 基于setbuf的ret2libc
  • 终于开通博客啦!
  • 工业主板:智慧工业时代的 “硬核大脑”
  • 2025 年冷凝器源头厂家最新推荐榜:优选凸显高真空稳定运行优势,助力企业精准选购平板/片式/方形/搪瓷方形/搪瓷方形平板冷凝器厂家推荐
  • WPS内部版
  • 2025 年管道生产厂家最新推荐排行榜:聚焦多行业适配需求,甄选技术领先、口碑优良的企业搪玻璃/搪瓷三通/搪瓷塔节/搪瓷弯头管道厂家推荐
  • 【51单片机篮球记分器+复合按键操作】2022-12-22 - 指南
  • npm ERR! chromedriver@2.46.0 install: `node install.js`
  • Java 实现 MySQL 同机 异机自动备份到 MinIO(附完整代码)
  • 为什么现在入行 Salesforce 更难了?真相在这里
  • Android 资源适配踩坑记:为什么我的设备匹配不上对应的 `values-wXXXdp-hXXXdp`?
  • QT实现DockWidget内部组件自动换行布局
  • 2025年知名的工业防锈漆厂家最新推荐榜 - Di
  • java8以上快速生成wsdl
  • 2025 年 10 月深圳市激光雕刻机厂家解析,基于专业技术及市场分析
  • UMDF驱动开发入门:二 详解INF文件与设备类选择
  • 2025年诚信的光学真空镀膜机厂家推荐及选择指南 - Di
  • 2025 蛋白/8秒液体/发膜推荐榜:玛丝兰 5 星领跑,这些修护力出众的品牌值得囤!西安悦己容凭技术实力登顶
  • 2025年耐用的破碎机TOP厂家推荐
  • 2025年知名的雕塑推荐TOP品牌企业 - Di
  • 美股及墨西哥股票数据接口文档
  • Spring - 教程
  • 例子:vue3+vite+router创建多级导航菜单
  • 2025 - Di
  • JVM探究(Leo)
  • Higress v2.1.8:30 项引擎更新 + 4 项控制台更新