分考场

问题描述

　　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

样例输出

Algorithm

万能的搜索，但是这里要回溯剪枝，最好也别用，vector应该也可以用，最开始我超时的原因因该是没有剪枝。

AC

 1 /*
 2 - 动态数组超时...... 
 3 */
 4 #include<iostream>
 5 #include<cstring>
 6 
 7 using namespace std;
 8 
 9 const int MAX = 109;
10 
11 // 邻接矩阵
12 int v[MAX][MAX];
13 // 考场里面的人
14 int room[MAX][MAX];
15 // 每个考场的人数
16 int len[MAX]; 
17 int n, m, ret = MAX;
18 
19 // 回溯 
20 void DFS(int x, int r)
21 {
22     // 多了这么一句剪枝, 就多通过的60%的数据... 
23     if(r >= ret) return;
24     if(x == n+1){
25         ret = min(r, ret);
26         return;
27     }
28     for(int i=1;i<=r;i++){
29         bool t = true;
30         int j = 0;
31         for(;j<len[i];j++){
32             if(v[x][room[i][j]]){ // 有认识的人 
33                 t = false;
34                 break;
35             }    
36         }
37         if(t){ // 没有认识的人 
38             len[i]++;
39             room[i][j] = x;
40             DFS(x+1, r);
41             len[i]--;
42             room[i][j] = 0;
43         } 
44     }
45     // 新开一间教室 
46     len[r+1]++;
47     room[r+1][0] = x;
48     DFS(x+1, r+1);
49     len[r+1]--;
50     room[r+1][0] = 0;
51 }
52 
53 int main()
54 {
55     while(cin>>n>>m)
56     {
57         int a, b;
58         memset(v, 0, sizeof(v));
59         memset(room, 0, sizeof(room));
60         memset(len, 0, sizeof(len));
61         while(m--)
62         {
63             scanf("%d%d", &a, &b);
64             v[a][b] = v[b][a] = 1;
65         }
66         // 最开始想从1号考场开始搜, 但是只能过80%
67         // 从0开始的话时间居然直接暴跌, 通过了... 
68         DFS(1, 0);
69         cout<<ret<<'
';
70     }
71     
72     return 0;
73 }

View Code

2019-03-05

18:32:39