#藍橋#JAVA#分考場
題目描述
n個人參加某項特殊考試。
為了公平，要求任何兩個認識的人不能分在同一個考場。
求是少需要分幾個考場才能滿足條件。
輸入描述
輸入格式：
第一行，一個整數n(1≤n≤100)，表示參加考試的人數。
第二行，一個整數m，表示接下來有m行數據。
以下m行每行的格式為：兩個整數a,b,用空格分開 (1≤a,b≤n)表示第a個人與第b個人認識。
輸出描述
輸出一行一個整數，表示最少分幾個考場。
問題分析
本題的核心問題是在給定一定數量的學生以及學生之間的認識關系的情況下，找出使用最少考場來安排所有學生的方案，并且要保證每個考場內的學生彼此都不認識。由于需要探索所有可能的考場安排組合，從中找出最優解，所以可以采用深度優先搜索（DFS）算法來解決。
1. 窮舉所有可能的方案
在這個問題中，每個學生都有多種選擇，可以被安排到已有的某個考場，或者新開一個考場。因為學生數量和考場安排的可能性眾多，要找出使用最少考場的方案，就需要遍歷所有可能的安排方式。DFS 算法的特點是能夠按照一定的順序，遞歸地深入搜索每一種可能的路徑，從而實現對所有可能方案的窮舉。 例如，對于第一個學生，它可以被安排到第一個考場；對于第二個學生，它可以選擇和第一個學生在同一個考場（前提是他們不認識），也可以新開一個考場。通過 DFS，我們可以依次嘗試所有這些可能性，確保不會遺漏任何一種安排方案。
2. 回溯機制
便于嘗試不同選擇 DFS 算法具有回溯機制，這在本題中非常有用。當我們將一個學生安排到某個考場后，繼續遞歸安排后續學生。如果后續發現這種安排方式無法滿足所有學生的安排或者不是最優方案，我們可以通過回溯操作撤銷之前的安排，嘗試其他的安排方式。 在代碼中，當我們將學生 `x` 安排到 `nums[i][j]` 座位后，遞歸調用 `dfs` 方法安排下一個學生。如果后續的遞歸過程中發現這種安排不行，返回后會將 `nums[i][j]` 置為 0，即撤銷該安排，然后嘗試將學生 `x` 安排到其他考場或座位。
3. 剪枝優化提高效率
在搜索過程中，我們可以利用剪枝策略來減少不必要的搜索。在本題中，如果當前使用的考場數量已經大于等于之前記錄的最少考場數量，那么繼續搜索下去不可能得到更優的方案，此時可以直接返回，避免繼續深入搜索，從而提高算法的效率。 例如，在 `dfs` 方法中，當 `k >= sum` 時，就直接返回，不再進行后續的搜索。
4. 遞歸實現
簡單直觀 DFS 算法通常使用遞歸的方式實現，代碼結構清晰，邏輯簡單直觀。在本題中，通過遞歸調用 `dfs` 方法，不斷地安排下一個學生，同時更新考場數量，使得代碼的實現和問題的解決思路高度一致，易于理解和維護。 綜上所述，由于本題需要窮舉所有可能的考場安排方案，并且需要回溯機制來嘗試不同的選擇，同時可以利用剪枝優化提高效率，因此使用 DFS 算法是一個合適的選擇。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {static int sum = 110;// 最多可以安排的教室static int nums[][] = new int [100][100]; //nums[i][k] 考場表 i 表示考場，k表示座位 static boolean visi[][] = new boolean [100][100];// 記錄考場信息static int n; // 學生數量static int m; // 關系數據的數量static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));public static void main(String[] args) throws IOException{String [] sc = bf.readLine().split(" ");n = Integer.parseInt(sc[0]);sc = bf.readLine().split(" ");m = Integer.parseInt(sc[0]);for (int i = 0; i < m ; i++){sc = bf.readLine().split(" ");int x = Integer.parseInt(sc[0]);int y = Integer.parseInt(sc[1]);// 標記互相認識的人visi[x][y] = true;visi[y][x] = true;}dfs(1, 1);System.out.println(sum);}// x 代表第幾個學生, k考場public static void dfs(int x,int k){// 剪枝 如果當前考場大于最小考場，就沒必要繼續則返回if(k >= sum) return;// 第x學生>全部學生，表明全部的學生都進入了考場，所有學生都有考場if(x > n){sum = Math.min(k, sum);//只需從當前考場值和當前最小值中取最小值return;}//為每一位學生分配考場for (int i = 1; i <= k; i++){int j = 0;//考場有人且無認識的人//i代表考場 j 代表座位號 while(nums[i][j] != 0 && !visi[x][nums[i][j]]){j++;}//考場為空if(nums[i][j] == 0){// x 進入nums[i][j]考場nums[i][j] = x;//下一位同學進行分配dfs(x + 1, k);//回溯 以便找到更好的方法nums[i][j] = 0;}}// 開辟完所有的考場發現都認識那就只可以再開一所考場了nums[k + 1][0] = x;dfs(x + 1, k + 1);//回溯nums[k + 1][0] = 0;}
})
