分考场（无向图着色问题）（dfs回溯）-白红宇

分考场（无向图着色问题）（dfs回溯）

阅读量：5308 次

发布时间：2019-06-14

本文共 1813 字，大约阅读时间需要 6 分钟。

问题描述

　　n个人参加某项特殊考试。

　　为了公平，要求任何两个认识的人不能分在同一个考场。

　　求是少需要分几个考场才能满足条件。

输入格式

　　第一行，一个整数n(1<n<100)，表示参加考试的人数。

　　第二行，一个整数m，表示接下来有m行数据

　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。

输出格式

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

样例输入

1 2

1 3

1 4

2 3

2 4

2 5

3 4

4 5

样例输出

样例输入

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

样例输出

解题思路：给你一个无向图，任意相邻节点颜色不相同的最少用颜色的数目，题目范围比较小，可以直接搜索，对于每一个人，我们搜索它可放房间的所有情况，注意剪枝。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   #include
                    
                     using namespace std;typedef long long ll;#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]const int INF=0x3f3f3f3f;const double PI=acos(-1.0);const double eps=1e-6;const ll mod=10007;const int maxn=1000005;ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}ll lcm(ll a,ll b){ return a/gcd(a,b)*b;}const int dir[4][2]={ { 1,0},{-1,0},{ 0,1},{ 0,-1}};int ans,n,m,q,tot,cnt[105],vis[105][105],mp[105][105];//cnt[i]表示第i个房间当前人数，mp[i][j]表示第i个房间的第j个人的编号void dfs(int id,int sum){ //id表示当前分配的为编号为id的人，sum表示当前已分配房间数目为sum个 if(sum>=ans)return; //已经超过当前最优值，剪枝 if(id>n){ ans=min(ans,sum); return; } for(int i=1;i<=sum;i++){ int tmp=0; for(int j=1;j<=cnt[i];j++){ if(!vis[id][mp[i][j]]) tmp++; else break; } if(tmp==cnt[i]){ //当前房间可行，放置 cnt[i]++; mp[i][cnt[i]]=id; dfs(id+1,sum); mp[i][cnt[i]]=0; //回溯 cnt[i]--; } } sum++; cnt[sum]++; mp[sum][1]=id; dfs(id+1,sum); //开一个新房间放置 mp[sum][1]=0; cnt[sum]--; sum--; return;}int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; ans=n; while(m--){ int u,v; cin>>u>>v; vis[u][v]=vis[v][u]=1; } dfs(1,0); cout<
                     
                      <