爆0的一天..

题意:混合图求欧拉回路问题

求多笔画问题 问最少几笔可以覆盖整张图所有边 图是混合图 数据范围1e4边数5e4

费用流暴力增广会tle 应该使用多路增广 来加快速度 但据说不一定所有图多路增广都快

暴力:

分部分分分别采用状压或欧拉回路性质

考虑无向图欧拉回路问题 一定是点度数位奇数的会增加一条路径  注意成环的情况需要将最后答案与1取max 有向图欧拉回路计数 是直接用所有入度比出度多的差/2即可 证明可以考虑上下界网络流

 

正解 考虑bzoj bridges那个问题 将每个点拆点考虑入度和出度的不同 先对无向图随机定向 然后建图跑网络流 流量为1 则为这图反向 考虑度数为奇数还有偶数之间的边 如果反向就会给原图带来1的正收益 度如果恰好是1和-1  那么显然反向不会对答案造成影响 但有可能对整体的答案造成影响 所以该边仍需要建出 考虑将有影响的边费用变成1此外如果该点度数为偶数 那么说明该点连的边反向之后还有一次可以反向的机会虽然不会对答案造成贡献  跑最大费用最大流即可注意 数据中可能存在自环或者是本身就构成一个欧拉回路的情况 所以使用并查集维护连通块 最后判断的时候如果该边流量还存在说明一开始定向的时候答案已经计算 反之就要检查这个是否是一个欧拉回路

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论