网站建设与维护/外贸网站seo教程

这两天对胡伯涛的论文进行了全面的学习,写一下笔记

1.网络流与01分数规划结合的一般问题

01分数规划可以配套网络流中的最大流,最小割神马的

网络战争
按照论文中推导的公式做即可,但是不好写QAQ没有写过容量为负的;解决办法为对于负的容量直接加到最小割答案中去,而不建边

最优标号
这题和去湖南的一道题很相似,不,就是一样的,对二进制上每一位求最大流,这题已经算不得01分数规划了吧

2 最大权闭合子图问题,构图思想

闭合子图即一个点集,点集所有点的出边都指向这个点集内部,是允许超过一个联通块的

解决最大权问题的构图方法为
对于已经存在的边,容量设置为+oo
新设源点S与汇点T,
对于正权的点v,连接(S->v)容量为点权
对于负权的点v,连接(v->T)容量为点权的绝对值
按此方法构图求最小割即可得到最大权的闭合子图

最大获利
感觉还是最小割思路好想

3 最大密度子图的最大权闭合子图模形和01分数规划方法

有时子图的密度是指无向图边数与点数的比值,有两种解决办法

①二分+最大权闭合子图
对于这个问题显然也需要01分数规划
设二分答案为M
构图如下
点集为原图点集,点权为1与所有的边(即将边看做点)边权为-M
边集为所有代表边的点向它的两个端点链接一条有向边
可以直观地看出,如果选择一条边,那么这条边的两个端点必然也被选择,那么就是一个闭合子图的模形.
②二分+最小割
论文中通过一系列证明,找到了更优复杂度的方法,即最小割(因为点数减少了)
证明采用了补集转换的思想
构图如下
新增源汇S,T
对于每一个点v
S -(U)-> v
v -(U+2*M-d_v)-> T
u -(1)-> v
其中的d_v为点v的度数
h(g) = (U*n-mincut)/2.0
实现中h(g)是不可能为负数的,因此当h(g)>0时当前答案小于最优解,否则大于等于最优解.
最后寻找哪些点被选时,选择比答案稍微小的答案跑网络流(即h(g)>0),再在残量网络上找出S集合

无向图中边带权的情况
此时子图密度被定义为边权和与点数的比

因为与不带权时类似构图时只有边权改变.所以沿用模型
u -(W_e)-> v
s -(U)-> v
v -(U+2*g-d_v)-> t
此时的d_v重新定义为与之相连的边的边权和

点边都带权的情况
此时子图密度被定义为边权和加点权和与点数的比

同样类似,只有边权改变
u -(W_e)-> v
s -(U)-> v
v -(U+2*g-d_v-2*P_v)-> t
d_v同上,p_v表示点权

题目

生活的艰辛
第一种情况

最大获利
将用户群看成边,边权为W_e,将中转站看作点,点权为p_v,此时这个题并不是裸的模形,因为最优化目标为一个减式(参见论文)但是却与点边都带权的情况最终优化目标可以转化,故同样可以利用最小割解决.可是闭合子图又好想又好写,让我怎么割舍~

4 用网络流解决二分图问题

二分图最大权匹配
最大流即可

二分图最小权覆盖集
X -(+oo)-> Y
S -(W_x)-> X
Y -(W_y)-> T

二分图最大权独立集
因为独立集与覆盖集互补
所以最大独立集 = 总权值-最小覆盖集

题目

有向图破坏
一条边会被两个端点中的一个删去,若想所有边删去,就是最小权覆盖咯

王者之剑
这题还是论文证的比较好…二分图最大权独立集,即每一个点向四周的点连边,此时一定会形成一个二分图,对此求二分图最小权覆盖,再用总权值减去这个权值就得到了最大权独立集
UPD:刚开始姿势不太好,用的拆点,没有黑白染色,结果慢了两倍..

5 其它注意
1. 满流边不一定是最小割中的集合,一定要通过dfs来求得S与T集合
2. 网格图是二分图
3. 多借助数学公式以达到数形结合