「中国邮路问题」Cards Ext与中国邮路问题

中国邮路问题

这个题我大概永远都不会出出来了所以我就把它写在博客里吧

~~如果有人没题出可以拿走坑害同学~~

题目大意：给定一个长度为n(n≤400)的01序列，每次你可以选择一个区间[l,r]，将[l,r]区间翻转（即，0变成1，1变成0），并支付al,r的代价。现在给定所有的al,r，求将整个序列变为0的最小代价

题目来源：JOI201X cards

问题转化

首先把序列差分一下，每个值异或一下后面，然后区间翻转就变成了翻转两个点

然后我们就可以建出一张无向图，每个区间变成连接两个点的一条边，边权为这个区间的翻转代价

我们令所有1为关键节点，那么显然关键节点有偶数个，不妨设为k。

我们选的区间要让所有关键节点被翻转奇数次，所有非关键节点被翻转偶数次。

问题转化成了，给出一张无向图，求这个无向图的边权和最小的生成子图，使得所有k个关键点度数为奇数，所有非关键点度数为偶数。

问题求解：

我们来证明：最优解的生成子图一定可以表示成k/2条最短路的和

显然这个生成子图里一定没有环，因此它是一座森林。任选一棵树，随便选两个叶节点x和y，将x到y在树上的路径从树上扒下来，变成x到y的最短路，答案不会变大。剩下的部分还是一个森林，我们一条一条扒下去，最后就会得到k/2条最短路。证毕。

然后做法就是，先用Floyd算法跑出任意两点间的最短路，然后带花树跑出最小权匹配，结束

本来想要出这个题的结果带花树太难写找不到地方出题，最后把这个题连算法一通打包丢给TKD让他去出51nod了……结果是啥我自然不知道了

然后我上了大学，学完了中国邮路之后，原来这个IDEA二十万年前就有了啊。。。

无向图中国邮路问题：给定一张带权无向连通图，求从起点出发经过每条边至少一次并回到原点的最短路径

问题等价于让某些边一条变多条使得图存在欧拉回路，而欧拉回路在连通图上存在的充要条件是每个点度数为偶数。于是中国邮路的边减掉原图的边，得到的就是原图的一个生成子图，使得所有原图的奇度点的度数为奇数，原图的偶度点的度数为偶数……

行了，Floyd+带花树可以上了，时间复杂度O(n3)

顺带一提，有向图上怎么做？

有向图上好做多了……

无向图是因为所有奇度点都一样所以必须上带花树这种大杀器，而有向图哪些点该加入度哪些点该加出度是知道的，费用流直接上就行了……

时间复杂度O(费用流)