题解

思路

先确定每个目标得分出现多少次，从而得到最短得分序列；再实现该竞赛图。

做法

将得分排序为 $v_1<\cdots<v_m$，令 $x_i\ge1$ 为 $v_i$ 的出现次数。顶点数为 $n=\sum x_i$，度数和必须为 $n(n-1)/2$。Landau 判据要求排序后每个真前缀的度数和不少于前缀点数的二项式系数。

子任务 1 枚举至多七个顶点的全部边方向。子任务 2 枚举重数向量并用 Landau 判据剪枝。满分做法对处理到的得分、已用顶点数与度数和做动态规划，同时检查新加入同分顶点形成的全部前缀，最后选择最小的 $n$。

得到度数序列后，为每一对顶点建立一个“边结点”，它向两个端点各连容量一的边；端点向汇点连接容量等于目标出度的边。满流选择了每条无向边的获胜端点，从而直接得到邻接矩阵。

正确性

动态规划枚举了每个目标得分的所有正重数，并且恰好保留满足 Landau 所有真前缀不等式的状态；终态再验证总度数和，因此得到且只得到可实现的得分序列。按顶点数从小到大选择终态保证最小性。流网络为每对顶点恰选一个获胜端点，并精确满足每个顶点的出度，故输出矩阵是所需竞赛图。

复杂度

满分做法的重数动态规划状态上界为 $O(m\cdot61\cdot1831)$，转移额外枚举重数；构图网络含 $O(n^2)$ 个结点与边，且 $n\le61$。