显然条件相当于任意三点 $u,v,w$ 有 $C(u,v)\ge \min\{C(u,w),C(v,w)\}$。求出最大生成森林，令 $C(u,v)$ 为 $u$ 到 $v$ 路径上边权最小值 (不连通则为 $1$) 即可。若有给定的边不满足则无解。
时间复杂度 $O(n+m\log m)$。
QOJ.ac
QOJ
Discussion #346 for Problem #3302. Just Meeting
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:13:41
Last updated: 2025-12-14 07:13:44
题解
Comments
No comments yet.