藍橋杯 曆屆試題 分考場

傳送門

這道題，暴力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;
}