作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 演算法 图论
时间Mon Sep 23 00:52:13 2019
https://i.imgur.com/86wzad1.jpg
请问第三小题的叙述一定成立吗？
立宇老师上课是说maximal flow problem拿来解决所有有理数，那maximal flow不是应该有
可能有分数吗？
第47题
https://i.imgur.com/WveKymu.jpg
请问这题的是要做什麽？看不懂题意
第43题第2小题的(c)选项
https://i.imgur.com/ePS3fSn.jpg
https://i.imgur.com/uYcTt3e.jpg
虽然我直觉选下去了但我看不懂@@
请问w(ai)<=w(ei)是什麽意思？ 为什麽G中的任意点ai也会有权重？
我看题目并没有更新过G中各点的权重，回去翻kruskal's也没有调整过点的权重啊@@
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.137.50.75 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1569171135.A.395.html
1F：推 FRAXIS: 一般都只讨论整数的情况 因为分数你只要全部乘以最小公倍09/23 10:31
2F：→ FRAXIS: 数就变成整数了09/23 10:31
3F：推 FRAXIS: 47 题就只是问当 edge weight 有上限时 如何实作09/23 10:33
4F：→ FRAXIS: priority queue 来加速09/23 10:33
感谢F大！
另外再请教一下为什麽第二小题在这种情况下会用到双向链结呢？看不懂解答的建法为什麽
是这样子
补充另一半的解答
https://i.imgur.com/vhSMZrS.jpg
刚刚有翻到原文书的intergrality theorem这边
https://i.imgur.com/VS6gxpW.jpg
所以我可以理解为
若图上所有边的capacity为整数，则使用ford fulkerson会得到最大流量f为整数，且对於
所有在图上的点u,v，u到v的流量为整数
但其实流量f的解并不一定必需是整数，只是用ford-fulkerson跑出来会是，这样对吗？
哦哦哦，犯蠢了，感谢mi大
※ 编辑: mistel (223.137.50.75 台湾), 09/23/2019 13:04:29
※ 编辑: mistel (223.137.50.75 台湾), 09/23/2019 13:14:59
7F：推 mi981027: 嗯嗯对的（话说原来书上有这个定理@@该添购了） 09/23 16:07
8F：→ mistel: 课本上通常一个算法大概Lenma加上定理应该有十多个XD，mi 09/23 17:53
9F：→ mistel: 大可以去compbook徵，蛮好徵的~ 09/23 17:53
10F：→ mathtsai: (1)对 maximum flow和是不是分数没关 09/23 20:19
11F：推 FRAXIS: 双向链结只是拿来存同 priority 的 nodes 09/23 21:51