algorithm - 如何确定联赛表是否可以接受？

Question

让我们考虑一个由 n 支球队组成的联赛，其中每支球队都与所有其他球队交手两次，结果可能有三种:赢、输或平。赢一场积 2 分，平一场积 1 分，输一场积 0 分。我们想决定是否可以采用联赛表。

我正在尝试实现一个多项式时间算法来解决这个问题。我考虑过使用网络流技术(如 Kleinberg 和 Tardos 的“算法设计”第 7 章中所述)，但无法提出任何具体的建议。

理想的解决方案是这样的

    IsAdmissible
    Input: Final league table
    {
         ...
    }
    Output: TRUE if there's a combination of matches resulting in given table
            FALSE otherwise

Answer 1

快速初步检查:所有队伍的分数总和必须满足:

• 20*19*2 ≤ 总和 ≤ 20*19*3

每支球队进行38场比赛，每场比赛可得0分、1分或3分。每支队伍的总分 s 必须满足:

• d + 3*w = s，其中d和w为非负整数(d - 平局数，w - 获胜数)
• d + w ≤ 38

很容易找到每个团队的所有有效 (d, w)。

如果每个团队都有一个有效的 (d, w)，那么该表是可以接受的，这样:

• 对于任何 2 个团队，sum(w) ≤ 38+36
  对于任何 3 个团队，sum(w) ≤ 38+36+34
  对于任何 n 个团队，sum(w) ≤ 38+36+...+(40-2n)

  (按分数递减对团队进行排序；对每个 n 执行一次检查就足够了)

• 总和(d) = 4560 - 2*总和(s)
• 总和(w) = 总和(s) - 1520

上面的两个等式是根据以下事实得出的:

• sum(s) = sum(d) + 3*sum(w)(平局 = 1 分，赢 = 3 分)
• sum(d)/2 + sum(w) = 20*19*2(每场比赛以一场胜利或两场平局结束)

所有这些条件都是必要的。我相信(但还没有证明)它们是足够的。