【人人都要学算法】网络流算法远比你想的要好玩

这个问题的由来是想起来明天将会有国足世预赛的比赛，于是今天去看了看国足目前在小组中的积分。在积分榜中，我们可以看到与中国同组的马尔代夫和不 丹都已经没有了出线的机会，即使他们剩余的比赛全胜也不可能出线了。我在想，有没有一个通用的方法，可以算出各支队还有没有出现的可能。

====

现在我们来回归正题：

网络流(network-flows)是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多 终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

其实网络流没有那么复杂，我们来用交通网示意图来举个例子：

我们来看这个交通网示意图，假设 S 为入口，T 为出口，图中的单向箭头表示从一个地方到另一个地方的可允许通过的方向，箭头上的数字表示该路线所能承载的最大的车流量（例如：a,b 两点，只能从 a 地到 b 地，并且该路线同时只能有4辆车同时通过）

我们需要解决的一个问题是如何安排好车的流量，例如现在有6辆车进入入口，我们可以如下图这样安排车的流量：

从图中我们可以看出来各个路线的最大承载量与当前的车流量，如上图的情况，我们说它是安全的。只要每一个地点它的驶入量与驶出量是相等的，我们就可以说它是安全的。另外，对于这个问题，我们会发现有的路线会是一个环（a->b->c->a）,我们暂且不考虑这个问题，我们只关注当前的交通系统是安全的，至于有的车可能一直在绕圈圈我们不会去考虑。

现在又出现了一个新的问题：现在的交通实际车流量并没有达到最大，似乎还能增大 S 点的驶入量，这时我们可以再寻找一条从 S 到 T 的路经：S->a->b->c->T。把每条路径的实际流量加1，我们会发现情况依旧是安全的，此时的驶入量为7：

现在实际交通流量达到最大了吗？这次好像没有那么容易看出来了。我们来看一下这条路经：S->b->a->c->T,我们 看到这条路经并不是完全顺着我们的路线的，只有 S->b 和 c->T 是顺着路线的，b->a 和 a->c 是逆着路线的。我们把顺着的路线流量都+1，把逆着的路线流量都-1，我们得到了下面的图：

此时，我们看这个图，它依旧是安全的，并且流量增加了1，现在驶入量是8。

现在我们得到了两种方式可以增大网络流流量的方法：

• 从 S -> T 寻找一条路径，每一条的子路径的承载量都未满，我们可以通过该路径增加流量。
• 从 S -> T 寻找一条路径，顺着方向的路径流量能+1（未满），逆着方向的路径流量能-1（非空），我们也可以通过该路径来增大流量。

我们把这两种路径叫做增广路径 ，如果我们不能在图中找到任何增广路径，那么我们就说它以及达到了最大流量。

====

现在，我们想想如何用网络流的模型来解决一支队是否有夺得第一名的可能。

现在我们来假设一种比赛，共有若干支队伍，互相之间要进行多场比赛，其中的5只队伍胜负情况如下表（其中 A 为联赛第一名，E 为联赛最后一名）：

剩余比赛的状况如下表：

我们现在考虑 E 队还有没有机会夺冠，也就是说在最好的情况下 E 能不能夺得第一名，即在剩下的比赛中 E 获得全胜。

现在我们考虑 E 如何才能夺得冠军，我们可以看到 E 还剩下27场比赛，如果它全胜的话，最后的胜局数量将会是49+27=76，那么也就是说，若使 E 保留夺冠可能，A 最多还能赢1场，B 最多还能赢4场，C 最多能赢7场，D 最多能赢16场。

现在我们来看看赛程，A、B 直接还有3场比赛，A、C 之间还有8场比赛，A、D 之间还有7场比赛，B、C 之间还有2场比赛，B、D之间还有7场比赛

我们把上述情况总结成一个网络流图：

我们来解释下这一个图：

从 S 点出发的路线表示某两只队之间的剩余比赛数，到 T 点的路线表示某队最多能赢的场数。例如，我们设置了一个 A-B 结点，然后从 S 引出一条道路指向这个结点，并将其最大流量设定为 3 ；再从这个结点出发，引出两条道路，分别指向 A 和 B ，其最大流量可以均设为 3 ，或者任意比 3 大的值（一般设为无穷大，以表示无需限制）。因而，在一个网络流中，结点 A-B 将会从源点 S 处获得最多 3 个单位的流量，并将所得的流量再分给结点 A 和结点 B 。如果把每个单位的流量理解成一个一个的胜局，那么网络流也就可以理解为这些胜局的来源和去向。类似的我们有 A-B,A-C,A-D,B-C,B-D 五个结点。因此这个图中的任意一个合法的网络流都表示一种比赛结果

因此，现在如果我们能使该图的最大流量到达27，那么我们就可以合理的安排比赛，使得每支队伍都不超过所能允许的最多生理场次。

现在图中的最大流量是26，我们看看还能不能增加一个流量，即找到一个增广路径（图中 n 表示无穷大）：

很显然，我们在图中找不到另外的增广路径了，因此该图的最大流量为26，因此，E 队不论多么努力，他们都将会与冠军无缘~。