题意
一个竞赛图的度数集合是由该竞赛图中每个点的出度所构成的集合。
现给定一个 (m) 个元素的集合，第 (i) 个元素是 (a_i) 。（此处集合已经去重）
判断其是否是一个竞赛图的度数集合，如果是，找到点数最小的满足条件的竞赛图，并构造方案。
(m, a_i le 30) ，(a_i) 互不相同。
题解
首先给出结论:假如给出每个点的出度,那么这些点能形成一个竞赛图当且仅当排序后的序列 (d_1, d_2, d_3, dots , d_n) 满足对于所有 (k < n) 有 (displaystyle sum _{k_i=1}^{k} d_i ≥ {k choose 2}) 且 (displaystyle sum_{i = 1} ^ {n} d_i = {n choose 2}) 。
考虑证明，不难发现对于竞赛图的任意点集 (S) ，都必须满足 (displaystyle sum_{i in S} d_i ge {|S| choose 2}) ，因为点集 (S) 之间的一对点至少会存在一条边贡献一个出度。
并且由于
所以发现最后的点数是 (O(max {a_i})) 级别的，其实最多就是 (2 max {a_i} + 1) 。
那么就可以 (dp) 了，先将给定集合中的元素从小到大排序。
设 (f[i][j][sum]) 表示考虑完前 (i) 个元素，当前图中已经有 (j) 个点了，度数之和为 (sum) 是否可行。
对于这个 (dp) 转移时枚举下一个元素出现了几次就行了。
然后我们只需要找到一个最小的 (i) 使得 (displaystyle f[n][i][{i choose 2}]) 满足就行了，这个就是合法点数。
似乎一定可以构造出方案。。不存在无解qwq 至于原因，可以去问 zhou888 。
然后需要构造方案，我们转移 (dp) 的时候多记一下当前如何转移的就行了，最后逆推回去就得到了度数可重集合。
然后我们用这个度数可重集合来构造答案，每次将度数从小到大排序，然后把第一个点向后面出度个点连边就行了，不难发现这样一定可以构造出一组合法解。
最后复杂度就是 (O(n{a_i}^3)) 的，可以通过qwq
总结
对于竞赛图可以考虑任意一个子集度数都不少于 (displaystyle {n choose 2}) 的性质。
然后考虑构造图的时候可以贪心的去暴力分配度数，或者用网络流模拟这个过程也行qwq
代码
用了 goto 以及 lambda 函数等骚操作。。
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("D.in", "r", stdin);
freopen ("D.out", "w", stdout);
#endif
}
const int Maxn = 35, N = 65;
bitset<2510> dp[Maxn][N], pre[Maxn][N];
int n, m, a[N], d[N], sum[N]; bitset<N> vis, G[N];
inline int Comb(int x) {
return x * (x - 1) / 2;
}
int main () {
File();
n = read();
For (i, 1, n) a[i] = read();
sort(a + 1, a + n + 1);
For (i, 1, n) sum[i] = sum[i - 1] + a[i];
dp[0][0][0] = true;
int pos = n;
For(j, 1, 61) For (i, 1, n) {
For (k, max(sum[i], Comb(j)), j * 30) {
if (dp[i - 1][j - 1][k - a[i]]) dp[i][j][k] = pre[i][j][k] = true;
if (dp[i][j - 1][k - a[i]]) dp[i][j][k] = !(pre[i][j][k] = false);
}
if (dp[n][j][Comb(j)]) { n = j; goto tag; }
}
tag: ;
int deg = Comb(n);
Fordown (i, n, 1)
d[i] = a[pos], pos -= pre[pos][i][deg], deg -= d[i];
int id[N], len;
For (i, 1, n) {
len = 0;
For (j, 1, n) if (!vis[j]) id[++ len] = j;
sort(id + 1, id + len + 1, [&](int lhs, int rhs) { return d[lhs] < d[rhs]; });
vis[id[1]] = true;
For (j, 2, d[id[1]] + 1) G[id[1]][id[j]] = true;
For (j, d[id[1]] + 2, len) G[id[j]][id[1]] = true, -- d[id[j]];
}
printf ("%d
", n);
For (i, 1, n)
For (j, 1, n + 1)
putchar (j == jend ? '
' : G[i][j] + '0');
return 0;
}