Description

一个竞赛图的度数集合是由该竞赛图中每个点的出度所构成的集合。 现给定一个 $m$ 个元素的集合，第 $i$ 个元素是 $a_i$。判断其是否是一个竞赛图的度数集合,如果是，找到点数最小的满足条件的竞赛图。

$1\le m\le 31$，$0\le a_i\le 30$，$a_i$ 互不相同。

Solution

这题好难啊，参考了别人的题解&代码。

首先，题目中提到的兰道定理：将出度数组 $d$ 升序排序。$1≤i≤n$​​ 时，$\sum^i_{j=1}d_i\leq \dfrac{i(i−1)}{2}$​。当且仅当 $i=n$ 时取等。

这可以用来判定竞赛图。

然后在本题中，套进去，可以得到 $n_{max}=61$。

然后考虑得到点数以及每个点的出度——跑一个完全背包。

$f(i,j,k)$ 表示集合中前 $j$ 个元素能否构成一个 $i$ 个点 $k$ 条边的竞赛图。

转移非常简单，$f(i,j,k)=f(i-1,j,k-a_j) \operatorname{or}f(i-1,j-1,k-a_{j-1})$。

实际转移用刷表更好写。

然后 DFS 回溯一下，可以得到每个点的出度。

接下来是如何构造竞赛图：

有一个比较贪心的思路：每次找一个剩余出度最少的点，向其他点依次连边，直到剩余出度为 $0$，接着让没被连边的点和它连一条边，最后删掉这个点。

正确性感性理解即可，还算直观。

Code

#include <algorithm>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 61, maxm = 1832;

int f[maxn + 3][maxn + 3][maxm + 3];
int pos[maxn + 3][maxn + 3][maxm + 3];
int n, a[maxn + 3], ans[maxn + 3];

void find_ans(int i, int j, int k)
{
    if (i == 0)
        return;
    ans[i] = a[j], k -= a[j];
    if (f[i - 1][j][k])
        find_ans(i - 1, j, k);
    else
        find_ans(i - 1, j - 1, k);
}

bool cmp(int x, int y) { return ans[x] < ans[y]; }

int e[maxn + 3][maxn + 3];

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    std::sort(a + 1, a + 1 + n);
    f[1][1][a[1]] = 1;
    for (int i = 1; i <= maxn; i++)
        for (int j = 1; j <= n; j++)
            for (int k = i * (i - 1) / 2; k <= maxm; k++)
                if (f[i][j][k])
                    f[i + 1][j][k + a[j]] = f[i + 1][j + 1][k + a[j + 1]] = 1;
    int res = 0;
    for (int i = n; i <= maxn; i++)
        if (f[i][n][i * (i - 1) / 2])
        {
            res = i;
            break;
        }
    if (!res)
    {
        cout << "=)" << endl;
        return 0;
    }
    cout << res << endl;

    find_ans(res, n, res * (res - 1) / 2);

    int pos[maxn];
    for (int i = 1; i <= res; i++)
        pos[i] = i;

    for (int i = 1; i <= res; i++)
    {
        std::sort(pos + i, pos + 1 + res, cmp);
        for (int j = i + 1; j <= i + ans[pos[i]]; j++)
            e[pos[i]][pos[j]] = 1;
        for (int j = i + ans[pos[i]] + 1; j <= res; j++)
            e[pos[j]][pos[i]] = 1, ans[pos[j]]--;
    }

    for (int i = 1; i <= res; i++, cout << endl)
        for (int j = 1; j <= res; j++)
            cout << e[i][j];
    return 0;
}