526互联

AtCoder Beginner Contest 310

发布时间 2023-07-16 21:31:35作者: Zeoy_kkk

Peaceful Teams

\(n\)个运动员，要分成\(t\)个队伍，一共有\(m\)对人不能放在一支队伍里，求方案数，每支队伍至少需要有一个人

\(1 \leq t \leq n\leq 10\)

题解：DFS搜索

  • 通过数据范围考虑爆搜
  • 我们考虑枚举的顺序\(O(n!)\)
  • 我们对每个人\(c\)枚举将其加到当前的\(d\)支队伍中
  • 新开一支空的队伍将\(c\)加到新的队伍中
  • 每次\(O(t)\)枚举检查每支队伍中是否有组队冲突
const int N = 2e5 + 10, M = 4e5 + 10;

int n, m, t;
int st[15][15];
vector<int> g[15];
int ans;

void dfs(int c, int d)
{
    if (c == n)
    {
        if (d != t)
            return;
        bool flag = true;
        for (int i = 0; i < t; ++i) // 枚举每支队伍
        {
            for (auto u : g[i])
            {
                for (auto v : g[i])
                {
                    if (st[u][v] || st[v][u])
                    {
                        flag = false;
                        break;
                    }
                }
                if (!flag)
                    break;
            }
            if (!flag)
                break;
        }
        ans += flag;
        return;
    }
    for (int i = 0; i <= d; ++i)
    {
        g[i].push_back(c);
        dfs(c + 1, max(d, i + 1));
        g[i].pop_back();
    }
}

void solve()
{
    cin >> n >> t >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        st[a][b] = st[b][a] = 1;
    }
    dfs(0, 0);
    cout << ans << endl;
}