您的位置: 首页 > IT文章 > poj3522 苗条树(极差最小生成树)

poj3522 苗条树(极差最小生成树)

分类: IT文章 • 2024-03-06 22:09:41

给你N个点和M条边要求你求出一个生成树使得这个生成树里边权极差最小

做法①

n*m做法

当最小的边已知的时候这个生成树就确定所以最大的边也确定了

于是我们每次枚举最小的边然后用kruskal做一遍得到答案

m*logn

LCT