返回信息流☆─────────────────────────────────────☆
weird (billmaths) 于 (Mon Apr 17 23:10:46 2006) 提到:
看过http://acm.hit.edu.cn/forum/viewtopic.php?t=871后，有些不明白的问题
1 残余网络的定义是什么？
2 “当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。”，这个能再具体解释一下么？
3 “带下界约束的最大流问题”和“循环流问题”，这两个没看懂
4 “二分图的最小权最大匹配”，觉得有问题
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Tue Apr 18 22:12:51 2006) 提到:
1 残余网络的定义是什么？
答:
容量网络 C, 流量网络 F, 残量网络 R
R = C - F
2 “当且仅当残余网络不包含负开销的有向环时，最大流才是一个最小费用流。”，这个能再具体解释一下么？
答:
存在负开销的有向环的话，我就可以原地转几个圈，减少总费用了
3 “带下界约束的最大流问题”和“循环流问题”，这两个没看懂
答：
没看过。
4 “二分图的最小权最大匹配”，觉得有问题
答：
常说的 二分图的最优匹配， 就是 km 算法
☆─────────────────────────────────────☆
weird (billmaths) 于 (Tue Apr 18 22:55:45 2006) 提到:
负开销是什么概念？
2.4 带下界约束的最大流问题
描述：求边有容量下限的网络的最大流。
解法：设边(u, v)的容量上下限分别为c, l，再添加一个源s'和汇t'，将(u, v)的下限去掉，上限改为c-l，增加两条边(u, t')，(s', v)，容量均为l。这样，将原网络带下限约束的最大流转换为双源点无容量下限的最大流。
例题：
2.5 循环流问题
描述：考虑无源也无汇的网络，设N是具有基础有向图D=(V，A)的网络，l和c是定义在A上的非负整数值且对任意边a，l(a)<=c(a)，分别称l和c为下容量函数和上容量函数。如果定义在A上的函数f满足：
f(v, V) - f(V, v) = 0, V中任意顶点v
l(a) <= f(a) <= c(a)
则称f为网络N的循环流。
对一般的网络N，循环流未必存在。给一个这样的网络，判断循环流是否存在。
解法：添加一个源s和汇t，对于每个下限容量l不为0的边(u, v)，将其下限去掉，上限改为c-l，增加两条边(u, t)，(s, v)，容量均为c。这样，原网络存在循环流等价于新s-t网络的最大流是满流。
以上是两个我没看懂的问题 “带下界约束的最大流问题”和“循环流问题”
我想问一下如何用最大流建模求解“二分图的最小权最大匹配”？
下面是那个文档的方法，我觉得不对，请看一下
3.2 二分图的最小权最大匹配
描述：利用最大流求一个二分图的最大匹配。
解法：已知一个二分图匹配问题，让所有的边从一个集合U指向另一个集合T，再添加一个源s和一个汇t，s有一条边指向U中所有顶点的边，t有一条边从T中所有顶点指向它自身，最后给图中所有边分配容量1。新s-t网络中的最大流对应于原二分图的一个最大匹配。
☆─────────────────────────────────────☆
sunmoonstar (秀) 于 (Wed Apr 19 08:46:50 2006) 提到:
负开销是什么概念？
答: 负开销就是小于 0 的费用之和, 一个负开销的环可以用来降低全局的费用
二分图的最小权最大匹配
答: 加一个源, 一个汇, 就是一个最小费用流的图了 ,就是 2516 的样子
和用最大流求二分图的最大匹配一样
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #954同步于 2006/4/21
ACM_ICPC机器人发帖
[合集] 询问几个网络流的问题
buptacm
2006/4/21镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。