蓝桥杯 历届试题 分考场

传送门

这道题，暴力dfs解决。

先开始乍眼一看题目我以为是并查集，后来想想发现没有连通传递性。

就用dfs来写就行。

c[i][j]表示第i个考场第j个人是谁。

mp[i][j]表示i和j是否有联系。

然后dfs部分传递两个参数，分别传递到了第几个人，到了第几个考场。

然后枚举考场，看看能不能把当前操作的这个人加到已经分好的考场中去，如果可以dfs下去（注意这里我们找到了也不能直接return，因为我们要找一个最优解）

如果没有找到的话只能新开设一个考场。

记得c[][]实时更新。

最重要的就是剪枝部分，没有减好就会tle.

因为数据最多到100，所以如果超过了100要直接return；

我们需要维护一个最小值，保存在ans中。条件是把这n个人全部都分配完成了。

最后输出即可~

代码部分：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;

int mp[N][N];
int c[N][N];
int n, m;
int a, b;
int ans = N;

void dfs(int x, int y)
{
	if (y >= ans)
	{
		return ;
	}
	if (x == n + 1)
	{
		ans = min(ans, y);
		return ;
	}
	for (int i = 1; i <= y; i++)
	{
		int k = 0;
		while (c[i][k] && !mp[x][c[i][k]])
		{
			k++;
		}
		if (!c[i][k])
		{
			c[i][k] = x;
			dfs(x + 1, y);
			c[i][k] = 0;
		}
	}
	c[y + 1][0] = x;
	dfs(x + 1, y + 1);
	c[y + 1][0] = 0;
}

int main()
{
	cin >> n;
	cin >> m;
	while (m--)
	{
		cin >> a >> b;
		mp[a][b] = mp[b][a] = 1;
	}
	dfs(1, 1);
	cout << ans << endl;
	return 0;
}