自动搬运

查看原文

来自洛谷，原作者为

	jojoxie **

搬运于2025-08-24 21:27:59，当前版本为作者最后更新于2018-09-23 21:38:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题我用了最普通的深搜来做

每个人挨个尝试，如果这个人与队中的任何人为仇敌则只能不选，否则尝试选与不选两种情况

听说不剪枝会TLE，但似乎没怎么剪枝还是AC了

#include <stdio.h>

int m, n, a[105];

int ch[105][105];//标记两个人是否是仇敌关系 

int x[105], tot = 0, s = 0;

void dfs(int k) {
	if(k > n) {
		if(s <= tot) {
			return;
		}
		tot = s;
		for(int j = 1; j <= n; j++) {
			a[j] = x[j];
		}
		return;
	}
	
	int check = 1;
	
	for(int t = 1; t < k; t++) {
		if(ch[t][k] && x[t]) {
        //如果现在已经选择的人中有人与第k个人为仇敌关系，则第k个人
        不能选 
			check = 0;
			break;
		}
	}
	
	if(check) {//如果第k个人可以选 
		x[k] = 1;
		s++;
		dfs(k + 1);//尝试选第k个人的情况 
		s--;
		x[k] = 0;
	}
	
	dfs(k + 1);//尝试不选第k个人的情况 
    
    return;
}

int main() {
	scanf("%d%d", &n, &m);
	
	int u, v;
	
	for(int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);
		ch[u][v] = 1;//标记u和v的仇敌关系 
		ch[v][u] = 1;
	}
	
	dfs(1);//从第一个人开始搜索 
	
	printf("%d\n", tot);
	
	for(int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	
	return 0;
}