题目大意

给定m个数的一个非负整数集合，不超过30。你需要构造一个竞赛图，满足：所有点的出度去重后等于该集合。
m≤31

分析

做这题我用到了兰道定理(Landau’s Theorem)。
设点i的出度为d[i]，那么对于任意$1≤i≤n$,有$\sum_{j=1}^{i}d[i]≥\frac{i(i-1)}{2}$。且当i=n时是等于。
那么可以考虑构造一个合法的d[]数组。每个数至少用一次，那么可以做一次背包。然后枚举点的个数，判断是否存在即可。
得到出度数组d[]后，依然是利用兰道定理来构造出竞赛图。主要思路如下：
1. 对于i>j，i向j连边，得到一个最初始的竞赛图，记它的出度数组为u[]。并且给d[]升序排序
2. 找到第一个满足$d[i]>u[i]$的位置，然后找到最大的j，满足u[i]=u[j]，接下来找到第一个满足$d[k]<u[k]$的位置，有$j<k$且$u[j]+2≤u[k]$，那么必然存在点x满足k向x连边且x向j连边。把这两条边翻转即可
3. 重复上面的过程直到d[]与u[]完全相同
关于兰道定理的具体内容可以上网搜

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;const int N=62,M=1832;typedef long long LL;int n,m,a[N],f[N][N][M],g[N][N][M],d[N],u[N];bool G[N][N];int main()
{scanf("%d",&m);for (int i=1;i<=m;i++) scanf("%d",&a[i]);sort(a+1,a+m+1);f[0][0][0]=1;for (int i=1;i<=m;i++)for (int j=i;j<N;j++)for (int k=i-1;k<j;k++)for (int y=k*(k-1)/2,x=(j-k)*a[i]+y;x<M;x++,y++) if (f[i-1][k][y]){f[i][j][x]=1; g[i][j][x]=j-k;}for (n=m;n<N && !f[m][n][n*(n-1)/2];n++);if (n==N){printf("=(\n"); return 0;}printf("%d\n",n);for (int i=m,j=n,k=n*(n-1)/2,x;i;i--){for (x=0;x<g[i][j][k];x++) d[j-x]=a[i];x=k; k-=g[i][j][x]*a[i]; j-=g[i][j][x];}sort(d+1,d+n+1);for (int i=1;i<=n;i++){u[i]=i-1; for (int j=1;j<i;j++) G[i][j]=1;}for (int i,j,k,x;;){for (i=1;i<=n && d[i]<=u[i];i++);if (i>n) break;for (j=n;u[j]!=u[i];j--);for (k=1;d[k]>=u[k];k++);for (x=n;!(G[k][x] && G[x][j]);x--);G[k][x]=0; G[x][k]=1; G[x][j]=0; G[j][x]=1; u[k]--; u[j]++;}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++) putchar(G[i][j]+'0');printf("\n");}return 0;
}