显然条件相当于任意三点 $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
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.