首页 > 代码库 > (转)一句话小结各种网络流)
(转)一句话小结各种网络流)
最大流:DINIC or SAP
最小费用最大流:SPFA+增广(费用的值较离散) or ZKW(费用的值集中)
有源汇的上下界最大流:新建s‘, t‘,用(i, j, l, r)表示i到j有一条下界为l上界为r的边,将每条这样的边拆成(s‘, j, 0, l), (i, t‘, 0, l), (i, j, 0, r-l),加入边(t, s, 0, max)再从s‘到t‘求最大流,再去掉(t, s, 0, max)这条边,从s到t求最大流
有源汇的上下界最小可行流:基本同上,将最后一步改成从t到s反求一遍最大流来退流;也可以二分(t, s, 0, max)这条边的容量
有源汇的上下界最小费用可行流:拆边方法同上,从s‘向t‘求一遍最小费用最大流
有源汇的上下界最小费用最大流:基本同上,还要再s向t求一遍最小费用最大流(*这个是自己YY的,可能不对,求指教)
无源汇的最大流(无向图全局最小割):Stoer-Wagner算法
无源汇的所有点对间最大流:分治,在当前点集内随便选两个点求最小割,用这个割更新一遍所有跨在两边的点对(不一定只是当前点集内的点),再将自己的点集割成两部分,递归做
无源汇的上下界可行流:拆边,直接从s‘到t‘跑一遍最大流
无源汇的上下界最小费用可行流:拆边,直接从s‘到t‘跑一遍最小费用最大流
平面图最小割转最短路:将平面区域当成点,两个点之间的边权为原来这两个平面区域之间的边的容量,补上一条汇到源的正无穷边之后,求这条正无穷边的一边到另一边的最短路
还有吗?
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。