【AtCoder CF16G】Zigzag MST

其实以后见到MST的题目直接往kruskal上面想就行了。。

很巧妙啊。。这个zigzag的过程实际上没什么用

如果\(B_i\)与\(A_i+1\)的边被选用,那么\(B_i\)和\(A_i\)一定已经连通,所以相当于\(A_i+1\)和\(A_i\)的边

如果\(A_i+1\)与\(B_i+1\)的边被选用,那么\(A_i+1\)和\(B_i\)一定已经连通,所以相当于\(B_i+1\)和\(B_i\)的边

依此类推,就是个连续给相邻点加边的过程

于是用个(扫描线?)处理一下相邻点的最小边就可以了

说点什么

您将是第一位评论人!

提醒
wpDiscuz