over 2 years ago

题目链接:http://poj.org/problem?id=3694
分析:
我们考虑求出所有的边双,这些边双会构成树的关系,对于每一次操作我们就是插入一条边,假如它们在同一边双中,那么忽略,否则与其构成了一个环,这个环上的点都得删除。这题数据范围小,可以暴力,也可以树链剖分,当然最理想的是并查集路径压缩。
poj3694.cpp

← 三角剖分:sgu383:Caravans bzoj1060:[ZJOI2007]时态同步 →
 
comments powered by Disqus