我从我的书中练习算法问题，并遇到了这个问题：
您将获得一个有n个节点和m个边缘的定向网络G，一个源s，一个接收器t和一个从s到t的最大流量f . 假设每个边的容量是正整数，描述用于在以下两种情况中的每一种中更新流f的O（m n）时间算法 . （i）边e的容量增加1.（ii）边e的容量减少1 .
看起来它就像走过网络流边缘和调整流程一样简单，但我不认为它真的那么简单 . 维基百科仅提供O（n ^ 2 m）或O（n m ^ 2）的算法 . 任何帮助或想法将不胜感激 .
有一个解决方案here .
假设e是u和v之间的边 .
增加容量的想法是简单地在残差流图中对从s到t的路径进行DFS .
如果在最大流量中未使用边缘，则完成 .
否则，我们的想法是在残差流图中查看是否存在从u到v的替代路径 . 这需要O（n m） . 如果找到，则可以将最大流量增加1 .
否则，您需要减少流量 . 你可以通过找到从u到s的路径，流量可以沿着该路径增加1，以及从t到v的路径，流量可以沿着该路径增加1.（增加的方向相反，因此减少了流量s到t） .
1 回答
有一个解决方案here .
假设e是u和v之间的边 .
容量增加
增加容量的想法是简单地在残差流图中对从s到t的路径进行DFS .
减少容量
如果在最大流量中未使用边缘，则完成 .
否则，我们的想法是在残差流图中查看是否存在从u到v的替代路径 . 这需要O（n m） . 如果找到，则可以将最大流量增加1 .
否则，您需要减少流量 . 你可以通过找到从u到s的路径，流量可以沿着该路径增加1，以及从t到v的路径，流量可以沿着该路径增加1.（增加的方向相反，因此减少了流量s到t） .