2014寒假总结(1.21)

Jan 21st

POJ 1904 King's Quest

求二分图中哪些边选取后还能构造出完备匹配。(数据范围 N<=2000)
对于所有的边,在新图中添加有向边
对于任意一条匹配边,在新图中添加有向边

在新图上求一次Tarjan,满足条件的边必定两端点在同一强连通分量内。问题解决

【AHOI2006】棋盘上的问题

第一步是贪心初始流。具体实现是维护一个类似于桶的东西,每个桶里维护同度数的链。每次选择度最小的点,在其邻域中选择度最小的点作为一条匹配边,然后在对应桶中删除并维护相应信息,直到无法操作为止。
对于初始后的流运用匈牙利算法对其进行增广,注意到一条边可删除的充要条件是在残余网络中该边两端点在同一强连通分量。所以对图进行缩点,然后统计答案。

对残余网络的理解加深:
1. 残余网络中流经任一回路,流量不变,方案改变。

<!--more--> 设该环路为 // 未完填坑

小白逛森林公园

基本的树链剖分,维护两类标记,整体标记与最大子段和标记。唯一值得注意的一点是如果偷懒不想写LCA,那么在爬树时一定注意最后那段的分类讨论,这个相当恶心。推荐以后写LCA版的。