P1692部落卫队

jojoxie · 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;
}