算法学习笔记(28): 网络流

刘德平 · 发表于 2022-12-8 07:33:37

比如说10条联结割1条水从割口处流出最大流就是割口处的流量假如这个管口的固定宽度是整数n 那么最大流就是n？

假如割9条那么只有一条可以流了是这个意思吧？

排排坐 · 发表于 2022-12-8 07:34:03

你不管怎么割，只要保证把源点和汇点完全隔绝开，那得到的流就是固定的啊。反正网络中只有那么多流。

青瓷器 · 发表于 2022-12-8 07:34:52

我的天啊总算看懂了今天看了十多篇整个人都懵逼了！ s到t是加法割是st中的减法所以由于有减法的存在 st的加法无法达到最大值当完全没有减法的时候加法达到最大值！

吕涛 · 发表于 2022-12-8 07:35:34

大佬您好，
在ff算法的 dfs函数中，在 for循环结束后，是不是要把 vis[p] 改回0 ？

是文鹏不是云鹏丶 · 发表于 2022-12-8 07:35:53

这也是重置vis的一种方法，我这里是直接memset统一重置了

蒋秋枫 · 发表于 2022-12-8 07:36:23

两层处理似乎都应该存在的。

外层的 memset，是用来彻底重置 vis数组的，以便开始一次崭新的 dfs搜索。

而在单次dfs搜索流程内，还需要在走错路时，通过 vis[p]=0, 将错路的节点释放出来。

想往未来 · 发表于 2022-12-8 07:36:45

并不需要。你再想一想，如果vis被置为1了，要么可以达到终点，就直接返回值了；要么不能达到终点，那么就没有必要走这条路，

吉利商用车 · 发表于 2022-12-8 07:37:06

我看懂了！
在这个问题中，就算不释放错误边上的点，也不会影响后续搜索的
感谢

别忘了我 · 发表于 2022-12-8 07:37:22

代码里面有while了，inline就没必要加了

孤岛渔夫 · 发表于 2022-12-8 07:38:15

其实都没必要加。现代的编译器在可以内联的时候基本都知道内联了，已经不需要专门标inline了。（这个代码写得比较早，那时候我还不知道这一点）

		自动登录	找回密码
密码			立即注册