Baseball Elimination

1. 问题描述

Princeton algorithms-part2第三周的编程作业：Baseball Elimination，给出各个参赛棒球队的比赛信息，利用算法分析出哪支队伍应该被淘汰。下面直接给出队伍会被淘汰的两种情况：

1.1 示例

i	team	w[i](wins)	l[i](loss)	r[i](left)	Atl	Phi	Ny	Mon
0	Atlanta	83	71	8	-	1	6	1
1	Philadelphia	80	79	3	1	-	0	2
2	New York	78	78	6	6	0	-	0
3	Montreal	77	82	3	1	2	0	-

每一行是各参赛队伍的比赛信息，其中:
w[i] 表示第i支队伍当前赢得场次
l[i] 当前输掉场次
r[i] 剩余比赛场次
g[i][j] 对应每行后4列，在剩余的比赛场次中，与其他各队伍的比赛次数
被淘汰的规则是：如果哪一只队伍在所有比赛结束时，仍不可能赢得最多场次(或并列)，即被淘汰。不考虑队伍退赛等特殊情况。

1.1.1 简单情况

例如球队Montreal，当前赢得场次77，剩余3次比赛，因此它在比赛结束时赢得的最多场次为80，仍然低于Atlanta当前得分83，因此应被淘汰。

1.1.2 复杂情况

乍看之下Philadelphia队在比赛结束时最多能拿到83场，恰好并列第一。但当Philadelphia队在比赛结束时赢得最多的话，就意味着Atlanta在剩余的8场比赛中一场也没有赢得，包括输掉了与New_York对决的6场比赛。这意味着什么呢？New_York会赢得6场比赛，并且最终得分为84，超越Philadelphia队，因此Philadelphia队实际应被淘汰。如何把像Philadelphia队这种漏网之鱼找出来呢，这就要用到Princeton algorithms-part2第三周介绍的算法max-flow.

2. 解决方法

2.1 建模

2.1.1 图中的结点

首先针对解决该问题的算法(max-flow)建立相应的数据结构————加权有向图。每次要评估一支队伍会不会被淘汰出局时，建立的图都是不一样的。图的结点包括一个只有出度的源结点s和一个只有入度的目标结点t,剩余的结点包括所有队伍(除了要评估的队伍)，所有要进行的比赛(不包括评估队伍参与的比赛)。这样我们可以来算一下图中会有多少结点，假设n支队伍，s和t2个结点，代表各队伍的结点n-1个，剩余的n-1支队伍中两两之间会有比赛，也就是有$ C_{n-1}^2 $个个结点，因此结点总数共有$ 2+(n-1)+C_{n-1}^2 $个，个人理解 : )

2.1.2 边的capacity

图中各边的capacity原文中有定义。s到各比赛结点边的的capacity为g[i][j](假设该比赛结点代表队伍i和j之间的比赛，capacity即为他们之间的比赛场数)，比赛结点到队伍结点之间的capacity认为无穷大，队伍结点到t间的capacity为评估结点最多赢得的比赛(当前得分加上剩余比赛场数)减去该队伍当前赢得比赛。

2.1.3 图的直观表示

假如说我们现在要对Philadelphia队进行评估，判断它是否要被淘汰出局，那么根据上述参赛队伍的信息，建立出来的图在直观上应该如下所示：

建立的图

2.2 评估方法

最后计算出前面所构建的图的max-flow后，如果所有来自s的边的flow都达到了它的capacity的话，则认为不存在队伍能在比赛结束时赢得比评估队伍更多的场次，即评估结果是不被淘汰；反之评估为淘汰。
小小的分析一下，这种解法还是很有道理的。假如一个队伍i评估的结果是不会被淘汰，那么其他所有队伍的最终得分都不应该超过这个被评估队伍可能的最大得分，即w[i]+r[i]。所以在剩余的比赛中(也就是从s点出发的各边的capacity之和)，每个队伍的得分都不能超过w[i]+r[1]减去他们自己的当前得分，这就是各队伍到t结点的capacity。
如果最终s点出发的各边flow都达到了capacity，说明这些队伍使尽了洪荒之力(完成了剩余所有比赛)最后取得的最好结果也只是和被评估的队伍势均力敌，那么被评估的队伍当然不应该被淘汰。
如果从s点出发的某些边的flow没有达到其capacity，说明剩余其他队伍有的还没完全发挥（没有完成剩余所有比赛），就已经赢到了被评估队伍最多可能赢得的场次，被评估队伍必然拿不到第一或并列第一了，所以此时应该被淘汰出局。
由于图的max-flow和最终来自s结点的所有flow之和相等，所以在实际写代码时，我们可以直接调用algs4库中的API，计算出所构建图的max-flow，并与来自s点的capacity之和比较大小即可得出评估结果。

3. 代码

完结撒花的同时，最后附上完整代码代码