D1T3用并查集对不对

先排序，从大到小加入每条边的的起点和终点，再查一下出发点和目标点在不在一起，在一起就输出本条边，预计能拿多少分

2025-04-13 23:43广告

话说我对拍暴力就是并查集的。。MS稍微优化下随机数据q = 500毫无压力啊。。

并查集按轶合并大概是可以ac的…

><这不就等于先生成一个最大生成树然后暴力吗。。。。

按秩合并AC

按秩合并+LCA
最大生成树+LCA
似乎都可以

整体二分+并查集似乎可AC

2025-04-13 23:43广告

并查集可以AC的

没套分治30，套分治AC

楼主很伤心啊，都已经排好序了，又去二分去了，估计WA10。一等又没了

弱弱问一下：按秩合并指的是启发式合并吗？
我觉得可以做两个并查集，一个用来维护MST 另一个用来维护q个问题。这样均摊似乎并不高？不过最坏应该还是O(mq)

下载贴吧APP
看高清直播、视频！

分享到: