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;
}
- Beginner AtCoder Contest 310beginner atcoder contest 310 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 315