题解：CF605B Lazy Student

zzmbj · 2025-10-29 21:47:53 · 题解

CF605B Lazy Student

题目传送门

管理员大大辛苦了！求求过一下/kel

题意

根据图中所有边的权值以及该边是否在最小生成树内构造一个无向无环图，如果没有满足条件的图输出 -1。

思路

• 对于 MST 边，连接从点 1 出发到新点的一条边。

• 对于非 MST 边：

  • 若需要连接的点超过了实际存在的点，输出 -1。
  • 当左端点追上右端点，左端点重置，右端点前进。

  这样的构造策略可以保证无环且充分利用每一条边。

代码

::::success[code] submission ::::