分考场（np完全问题，回溯法）

问题描述

　　n个人参加某项特殊考试。
　　为了公平，要求任何两个认识的人不能分在同一个考场。
　　求是少需要分几个考场才能满足条件。

输入格式

　　第一行，一个整数n(1<n<100)，表示参加考试的人数。
　　第二行，一个整数m，表示接下来有m行数据
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

　　一行一个整数，表示最少分几个考场。

样例输入

5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

样例输出

样例输入

5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

样例输出

基本思路：

回溯啊，一开始疯了没剪枝，后来想剪枝的时候发现想不到什么剪枝策略，就很难受，然后就加了一个最显而易见的剪枝就过了

代码如下：

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

const int maxn = 110;

const int inf = 0x3f3f3f3f;

int gra[maxn][maxn];

int cun[maxn][maxn];

int cnt[maxn];

int res=inf;

int n,m;

void solve(int id,int num){

    if(num>=res){

        return;

    }

    if(id>n){

        res=min(res,num);

        return;

    }

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

        int sz=cnt[i];

        int jishu=0;

        for(int j=1;j<=sz;j++){

            if(gra[id][cun[i][j]]==0){

                jishu++;

            }

        }

        if(jishu==sz){

            cun[i][++cnt[i]]=id;

            solve(id+1,num);

            cnt[i]--;

        }

    }

    cun[num+1][++cnt[num+1]]=id;

    solve(id+1,num+1);

    --cnt[num+1];

}

int main(){

    scanf("%d%d",&n,&m);

    memset(gra,0,sizeof(gra));

    memset(cnt,0,sizeof(cnt));

    while(m--){

        int a,b;

        scanf("%d%d",&a,&b);

        gra[a][b]=gra[b][a]=1;

    }

    solve(1,0);

    printf("%d\n",res);

    return 0;

}

巴特西

分考场（np完全问题，回溯法）

最新文章

热门文章