【NOI2009】变换序列

Source and Judge

luogu1963

Record

1h

Analysis

请先思考后再展开

不难转化为求二分图完备匹配中的字典序最小对应方案
匈牙利算法能很好地解决这个问题,从下往上枚举左边(越后优先级越高,类似基数排序),右边则从上往下
复杂度为n方,不会太满(当时网络流不普及,这个正解合情合理)
这时候就会有人想,为什么不dinic+一些建边顺序的调整呢,n根号呢
然而dinic是bfs一次后多路同时dfs,缺乏匈牙利算法那种不断推开别人的过程
一个显然的反例就是第一次就完备匹配

upd:rose爷爷给出了一个 O(n) 的做法
因为每个点只连出去两条边,把点化为两个选择之间的边,那么如果不是基环树(或基环森林)就无解
然后每个环的方向一定是相同的,环上挂的边一定是向外的,每个环独立地贪心即可
因为可以计数排序,所以线性

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/eed2.html
转载请注明出处,谢谢!