最大流问题为什么不能用贪心算法解决
答案:1 悬赏:60 手机版
解决时间 2021-04-05 13:36
- 提问者网友：孤凫
- 2021-04-05 07:09
最大流问题为什么不能用贪心算法解决
最佳答案
- 五星知识达人网友：何以畏孤独
- 2021-04-05 08:09
举个反例
下图
起点 终点 流量
1 2 2
1 3 1
2 3 1
2 4 1
3 4 2
S=1，T=4，最大流是3
但如果你第一次找到了1-3-2-4的路径，第二次就没路可走了，你找到的最大流就是1
下图
起点 终点 流量
1 2 2
1 3 1
2 3 1
2 4 1
3 4 2
S=1，T=4，最大流是3
但如果你第一次找到了1-3-2-4的路径，第二次就没路可走了，你找到的最大流就是1
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯
| 正方形一边上任一点到这个正方形两条对角线的 |
| 阴历怎么看 ？ |