洛谷 P1692 【部落卫队】

啊这道题其实暴力就行了，算是一道搜索入门题吧。

搜索变量就应该是当前到哪一位了，然后进行枚举，当前的一位加或者不加，然后知道搜完为止。

判断当前一位可不可以加的时候本来想用vector的，但是没调出来qwq（菜），然后学的第一篇题解惹

上代码：

#include <bits/stdc++.h>

using namespace std;

int n , m , ans;

int anses[110] , now[110] , vis[110] , dis[110][110];

void dfs(int step , int sum){	//当前到哪个人了和人数总和

	if(step == n + 1){

		if(sum > ans){

			ans = sum;

			for(int i = 1; i <= n; i++) anses[i] = now[i];

		}

		return;

	}

	if(n + sum - step + 1 < ans) return;	//剪枝，若剩下的还没有答案多，放弃

	int f = 0;

	for(int i = 1; i <= step - 1; i++)

        if(vis[i] && dis[step][i]){

			f = 1;

			break;

		}

	if(!f){

		vis[step] = 1;

		now[step] = 1;

		dfs(step + 1 , sum + 1);

		now[step] = 0;

		vis[step] = 0;

	}

	dfs(step + 1 , sum);	//！！！！这里不能交换与上面加入这个人的位置，因为在答案一致的情况下字典序优先

}

int main(){

	cin >> n >> m;

	for(int i = 1; i <= m; i++){

		int x , y;

		cin >> x >> y;

		dis[x][y] = dis[y][x] = 1;

	}

	dfs(1 , 0);

	cout << ans << endl;

	for(int i = 1; i <= n; i++) cout << anses[i] << " ";

	return 0;

}

吐槽：多刷点搜索暴力肯定有好处的，就像这次6.6欢乐赛一样，暴力可以拿很多分了

巴特西

洛谷 P1692 【部落卫队】

最新文章

热门文章