傳送門

題目描述

n個(gè)人參加某項(xiàng)特殊考試。
為了公平，要求任何兩個(gè)認(rèn)識(shí)的人不能分在同一個(gè)考場。
求是少需要分幾個(gè)考場才能滿足條件。

輸入

第一行，一個(gè)整數(shù)n(1<n<100)，表示參加考試的人數(shù)。
第二行，一個(gè)整數(shù)m，表示接下來有m行數(shù)據(jù)
以下m行每行的格式為：兩個(gè)整數(shù)a，b，用空格分開 (1<=a,b<=n) 表示第a個(gè)人與第b個(gè)人認(rèn)識(shí)。

輸出

一行一個(gè)整數(shù)，表示最少分幾個(gè)考場。

樣例輸入1

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

樣例輸出1

4

樣例輸入2

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

樣例輸出2

5

分析

• 做這道題的思路相對還是比較暴力的，數(shù)據(jù)不算大，直接用DFS枚舉出所有可能的分考場情況加上適當(dāng)剪枝，從中找出考場數(shù)最少的情況即可。
• 代碼核心思路：用一個(gè)第一維表示考場號(hào)、第二維表示考生編號(hào)的二維數(shù)組存儲(chǔ)分配已分配考場的學(xué)生，以學(xué)生編號(hào)1->n的順序給學(xué)生分配考場。首先判斷能不能在已有的把他分到已有的考場中，如果不能，就開新的考場再把該學(xué)生分進(jìn)去。
• 剪枝：如果當(dāng)前的考場數(shù)不小于前面找到的值就可以不必往下找了（小優(yōu)化）
• 如果下面代碼中的函數(shù)參數(shù)為dfs(1,1)則會(huì)有一組數(shù)據(jù)運(yùn)行超時(shí)，可以知道一開始考場數(shù)為0，要直接開新的考場會(huì)運(yùn)行會(huì)更加高效（被坑了很久）

代碼如下

import java.util.*; public class Main {static final int maxn=105;static int map[][]=new int[maxn][maxn];//用鄰接矩陣表示同學(xué)之間有沒有關(guān)系static int p[][]=new int[maxn][maxn]; //存儲(chǔ)i號(hào)考場的學(xué)生static int rs[]=new int[maxn]; //存儲(chǔ)i號(hào)考場的學(xué)生數(shù)目static int n,m;static int cnt=maxn;static void dfs(int x,int num) { //x表示學(xué)生編號(hào)，num表示考場數(shù)if(num>=cnt)return ; //剪枝，當(dāng)考場數(shù)大于現(xiàn)在找到的值就可以不必往下找了if(x>n) { //所有考生都分配到考場了cnt=Math.min(cnt, num);return ;}for(int i=1;i<=num;i++) { //遍歷已存在的考場int k=0;for(int j=1;j<=rs[i];j++) { //遍歷i號(hào)考場里面的學(xué)生if(map[x][p[i][j]]==0)k++; //判斷該學(xué)生和考場里面的學(xué)生有沒有關(guān)系}if(k==rs[i]) { //滿足條件p[i][++rs[i]]=x;dfs(x+1, num);--rs[i]; //回溯}}//需要開新的考場p[num+1][++rs[num+1]]=x;dfs(x+1, num+1);--rs[num+1]; //回溯}public static void main(String[] args) {Scanner cin=new Scanner(System.in);n=cin.nextInt();m=cin.nextInt();for(int i=0;i<m;i++){int x=cin.nextInt();int y=cin.nextInt();map[x][y]=map[y][x]=1;}dfs(1, 0); //dfs(1,1);會(huì)超時(shí)System.out.println(cnt);} }

代碼簡化

認(rèn)真思考了一下，似乎那個(gè)rs[]數(shù)組不是必要的，思路還是和上面一致，于是有了以下的簡化版dfs代碼。 但是似乎跑得更慢了（逃

static void dfs(int x,int num) {if(num>=min)return ;if(x>n) {min=Math.min(min, num);return ;}for(int i=1;i<=num;i++) {int k=0;while(map[x][p[i][k]]==0&&p[i][k]!=0)k++;if(p[i][k]==0) {p[i][k]=x;dfs(x+1, num);p[i][k]=0;}}p[num+1][0]=x;dfs(x+1, num+1);p[num+1][0]=0;}

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯 历届试题 分考场（DFS+枚举）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。