作者ybite (小犬)
看板Grad-ProbAsk
标题[理工] [Algo] 台大100-资工
时间Sat Feb 19 21:56:23 2011
还是趁着对题目有印象赶快发问...
这题不会，不过希望题目没记错
假若今天有一图形如下
┌┬┬┬┬┬┬┬┬┬┐
├●┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼●┼┼┼┤
├┼┼●┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼●┼┼┤
├┼┼┼┼●┼┼┼┼┤
├●┼┼┼┼┼┼┼┼┤
└┴┴┴┴┴┴┴┴┴┘
在这个图中，要判断每个●点都有一条和走到图形外围的路径，
且图形中不会出现两条路径共用同一边（只要证出是否即可）
举例来说：
┌┬┬┬┬┬
┬┬┬┬┐
├●┼┼┼┼
┼┼┼┼┤
├┼┼┼┼┼
●┼┼┼┤
├┼┼●┼┼┼┼┼┼┤
├┼┼┼┼┼┼┼┼┼┤
├┼┼┼┼┼┼
●┼┼┤
├┼┼┼┼
●┼┼┼┼┤
├●┼┼┼
┼┼┼┼┼┤
└┴┴┴┴
┴┴┴┴┴┘
真正的问题是：请把这个问题转成一个Maxmium Flow问题...
-------
本来以为很简单，但是Maxmium flow不是单向的吗？ @@
还是要做两次？ @@
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.131.201.249
※ 编辑: ybite 来自: 220.131.201.249 (02/19 21:57)
1F：推 juan19283746:我是写... S连到所有黑点 所有的外围边连到t 02/19 22:02
2F：→ juan19283746:然後其他点和编如同原图 全部边容量=1 02/19 22:02
3F：→ juan19283746:如果有流量>k的话 就可以ESCAPE 02/19 22:03
4F：→ juan19283746:应该不会差太多 可是我觉得应该有瑕疵 02/19 22:03
5F：→ juan19283746:就是方向的问题QQ 02/19 22:05
6F：→ ybite:我本来也想这样写，就是卡一个流量，所以没写下去... 02/19 22:17
7F：推 KiroKu:cormen的问题 流量=|v|就是有解 02/19 22:22
8F：推 cmuming:全部边容量=1的状况，等同允许一个点有两个in两个out 02/19 22:57
9F：→ ybite:理解，16分飞了qqqqqqqqqqqqqq 02/19 23:01
10F：推 nypgand1:请问"两个in两个out"是什麽意思阿? 可以举一个转过的图吗 02/19 23:43
11F：推 KiroKu:我觉得没差吧 a->B c->D路径有重叠的话 代表其实 a->D c->B 02/19 23:48
12F：推 cmuming:楼上如果发生"交叉"的话就不成立罗 02/20 23:05