在锦标赛中可能获胜的算法
Algorithm for possible win in a tournament
我正在准备考试，但遇到了这个问题：
We have n teams that play with each other twice. Each play ends without a draw. The team with the most wins is declared a winner (can be more than one). Design an algorithm that given some set of initial outcomes of plays checks whether a certain team still has a chance to become a winner in this tournament.
我不知道如何接近。该问题已归入 "Flows and matchings" 类别，但我不明白这怎么会是最大流量问题。
假设我们希望A队获胜。
显然，如果 A 赢得所有比赛是最好的，所以这给了我们一个目标分数。我们现在可以计算为了让 A 整体获胜，每个其他团队必须遭受的损失数量。
问题是我们在剩下的每场比赛中最多只能得到1个失败者。所以我们需要弄清楚如何将球队与比赛进行匹配，其中每场比赛对应于特定球队在特定比赛中的输球。
这基本上是团队和游戏之间的二分图匹配，但我们也可以通过额外的源和汇节点以最大流来解决它。
- 为每个团队创建一个源节点，其容量等于该团队必须拥有的损失数。
- 从每支球队到每场剩余的涉及该球队的比赛（具有无限容量）
- 从每个剩余的游戏到容量等于该游戏要玩的次数的汇聚节点建立边。 （即如果 B vs C 游戏仍要进行，则容量为 2）
那么如果你可以构建一个从源到汇的有效流达到容量（在每个源到团队边缘）你就证明了团队 A 仍然有可能获胜。
我正在准备考试，但遇到了这个问题：
We have n teams that play with each other twice. Each play ends without a draw. The team with the most wins is declared a winner (can be more than one). Design an algorithm that given some set of initial outcomes of plays checks whether a certain team still has a chance to become a winner in this tournament.
我不知道如何接近。该问题已归入 "Flows and matchings" 类别，但我不明白这怎么会是最大流量问题。
假设我们希望A队获胜。
显然，如果 A 赢得所有比赛是最好的，所以这给了我们一个目标分数。我们现在可以计算为了让 A 整体获胜，每个其他团队必须遭受的损失数量。
问题是我们在剩下的每场比赛中最多只能得到1个失败者。所以我们需要弄清楚如何将球队与比赛进行匹配，其中每场比赛对应于特定球队在特定比赛中的输球。
这基本上是团队和游戏之间的二分图匹配，但我们也可以通过额外的源和汇节点以最大流来解决它。
- 为每个团队创建一个源节点，其容量等于该团队必须拥有的损失数。
- 从每支球队到每场剩余的涉及该球队的比赛（具有无限容量）
- 从每个剩余的游戏到容量等于该游戏要玩的次数的汇聚节点建立边。 （即如果 B vs C 游戏仍要进行，则容量为 2）
那么如果你可以构建一个从源到汇的有效流达到容量（在每个源到团队边缘）你就证明了团队 A 仍然有可能获胜。