原創(chuàng)

---

分考場(chǎng)：http://lx.lanqiao.cn/problem.page?gpid=T457 問題描述 n個(gè)人參加某項(xiàng)特殊考試。
　　為了公平，要求任何兩個(gè)認(rèn)識(shí)的人不能分在同一個(gè)考場(chǎng)。
　　求是少需要分幾個(gè)考場(chǎng)才能滿足條件。 輸入格式 第一行，一個(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è)考場(chǎng)。 樣例輸入 5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5 樣例輸出 4 樣例輸入 5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5 樣例輸出 5 　　此題類似圖著色問題：https://baike.baidu.com/item/%E5%9B%BE%E7%9D%80%E8%89%B2%E9%97%AE%E9%A2%98/8928655?fr=aladdin， 一個(gè)無向圖著色，要求相鄰的點(diǎn)不能是同色，方案有多種，找出所用顏色數(shù)最少的方案即可解題。 　　著色過程是按點(diǎn)順序一一著色，n個(gè)點(diǎn)，一一按順序?yàn)辄c(diǎn)1~n著色，著色完一個(gè)點(diǎn)繼續(xù)著色下一個(gè)點(diǎn)，直至著色完n個(gè)點(diǎn)。 　　由于一個(gè)點(diǎn)可以多種合理的著色方案，不同的著色方案對(duì)最終的顏色種數(shù)影響是不同的，所以需要一一比較所有的方案，過程類似 深搜回溯。 1 import java.util.*; 2 3 public class Main { 4 5 static int n; //考試人數(shù) 6 static int m; //m個(gè)關(guān)系 7 static int matrix[][]; //鄰接矩陣 8 static int max=0; //用了的顏色數(shù) 9 static int pid_Color[]; //存儲(chǔ)點(diǎn)用了哪種顏色 10 static int flag=0; 11 static int res=99999; 12 13 static boolean judge(int pid,int color) { 14 for(int i=1;i<=n;i++) { 15 //鄰接點(diǎn)判斷 16 if(matrix[pid][i]==1) { 17 //判斷鄰接點(diǎn)是否涂色 18 if(pid_Color[i]!=0) { 19 //鄰接點(diǎn)顏色判斷 20 if(pid_Color[i]==color) { 21 return false; 22 } 23 } 24 } 25 } 26 return true; 27 } 28 29 static void color_Painting(int pid,int color_Num) { //pid代表點(diǎn),目前已經(jīng)用了color_Num種顏色 30 if(color_Num>=res) { 31 return; 32 } 33 if(pid>n) { 34 res=res<color_Num?res:color_Num; 35 return; 36 } 37 //枚舉顏色1~color_Num,看看可不可以用在點(diǎn)pid 38 for(int color=1;color<=color_Num;color++) { 39 //可以 40 if( judge(pid,color)==true ) { 41 pid_Color[pid]=color; //涂色 42 color_Painting(pid+1,color_Num);//涂下一個(gè)點(diǎn) 43 pid_Color[pid]=0; 44 } 45 } 46 //顏色1~color_Num都用不了,用新的顏色 47 pid_Color[pid]=color_Num+1; 48 color_Painting(pid+1,color_Num+1); 49 pid_Color[pid]=0; 50 } 51 52 public static void main(String[] args) { 53 Scanner reader=new Scanner(System.in); 54 n=reader.nextInt(); 55 m=reader.nextInt(); 56 matrix=new int[n+1][n+1]; //編號(hào)從1開始 57 pid_Color=new int[n+1]; 58 //讀入m個(gè)關(guān)系 59 for(int i=1;i<=m;i++) { 60 int a=reader.nextInt(); 61 int b=reader.nextInt(); 62 //無向圖 63 matrix[a][b]=1; 64 matrix[b][a]=1; 65 } 66 color_Painting(1,0); 67 System.out.println(res); 68 } 69 }

　　代碼2：

1 import java.util.*; 2 3 public class Main { 4 5 static int n; //學(xué)生人數(shù) 6 static int m; //關(guān)系 7 //鄰接矩陣 8 static int matrix[][]; 9 //room[i][j]=z代表教室room[i]的第j個(gè)座位坐著同學(xué)z 10 static int room[][]; 11 //room_num[i]存儲(chǔ)教室room[i]目前坐了多少位同學(xué) 12 static int room_num[]; 13 static int res=1000; 14 15 static void sit(int stu,int pos) { //stu表示第stu個(gè)學(xué)生,pos表示目前用了pos個(gè)教室 16 if(pos>=res) { 17 return; 18 } 19 if(stu>n) { 20 res=res<pos?res:pos; 21 return; 22 } 23 //判斷前面1~pos個(gè)教室能不能放入同學(xué)stu 24 for(int i=1;i<=pos;i++) { 25 //對(duì)于教室room[i],只要同學(xué)stu不認(rèn)識(shí)里面的其他所有同學(xué)即可放入,可以判斷stu在此教室不認(rèn)識(shí)的人數(shù)是否等于room_num[i] 26 int total=0; //統(tǒng)計(jì)stu在此教室room[i]不認(rèn)識(shí)的人數(shù) 27 for(int j=1;j<=room_num[i];j++) { 28 if(matrix[stu][room[i][j]]==0) { 29 total++; 30 } 31 } 32 //stu不認(rèn)識(shí)教室room[i]里面的所有人 33 if(total==room_num[i]) { 34 room[i][++room_num[i]]=stu; //放入stu 35 sit(stu+1,pos); //考慮下一位同學(xué),因?yàn)闆]有開辟新的教室,所以還是只用了pos個(gè)教室 36 //回溯的原因:學(xué)生stu雖然可以放在教室room[a],但也許可以放入room[b],這兩種放法對(duì)所需開辟的最小教室量是不同的,所以需要枚舉所有情況 37 room_num[i]--; 38 } 39 } 40 //來到此步,說明教室1~pos都放不下學(xué)生stu,必須開辟新的教室 41 room[pos+1][1]=stu; //將stu放入新的教室 42 room_num[pos+1]++; 43 sit(stu+1,pos+1); 44 room_num[pos+1]--; //回溯 45 } 46 47 public static void main(String[] args) { 48 Scanner reader=new Scanner(System.in); 49 n=reader.nextInt(); 50 m=reader.nextInt(); 51 matrix=new int[n+1][n+1]; 52 room=new int[101][101]; 53 room_num=new int[101]; 54 //讀入邊 55 for(int i=1;i<=m;i++) { 56 int one=reader.nextInt(); 57 int two=reader.nextInt(); 58 matrix[one][two]=1; 59 matrix[two][one]=1; 60 } 61 sit(1,0); 62 System.out.println(res); 63 } 64 65 }

16:53:43

2018-08-11

轉(zhuǎn)載于:https://www.cnblogs.com/chiweiming/p/9459726.html

總結(jié)

以上是生活随笔為你收集整理的分考场的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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