DFS-分考場

問題描述

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

輸入格式

第一行，一個整數n(1

輸出格式

一行一個整數，表示最少分幾個考場。

樣例輸入

<code>5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
/<code>

樣例輸出

<code>4
/<code>

樣例輸入

<code>5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
/<code>

樣例輸出

<code>5
/<code>

<code>
import java.util.Arrays;
import java.util.Scanner;

public class 分考場 {
    final static int max=100;
    final static int INF=0X3f3f3f3f;
    static int ans=INF;
    static boolean flag=false;
    static int que[][]=new int[max+5][max+5];
    static boolean vis[][]=new boolean[max+5][max+5];
    static int queMenber[]=new int[max+5];
    static int num=0;//考場數
    static int n,m,a,b;

    static void dfs(int p,int num){
        if (ans<=num){
            return;
        }
        if(p>n){//n表示5個人
            if (ans>num)
                ans=num;
            return;
        }
        for (int i = 1; i <=num ; i++) {
            flag=true;
            for (int j = 1; j <=queMenber[j] ; j++) {
                if (vis[p][que[i][j]]){
                    flag=false;
                    break;
                }
            }
            if (flag){
                queMenber[i]++;
                que[i][queMenber[i]]=p;
                dfs(p+1,num);
                queMenber[i]--;//回溯
                flag=false;//如果之前所有考場都不可以安排，則選擇新建一個考場  如果沒有這句可能不會新建考場
            }
        }
        if(!flag)//如果之前的考場都無法與p相容，那麼p新建一個考場 

        {
            num++;
            queMenber[num]=1;
            que[num][1]=p;
            dfs(p+1,num);//新建考場之後不用回溯，因為已經沒有其他可能，需要回溯的只會出現在有幾個已建考場都容納p時，選擇一種最優的
            //eg  5 4    1 3 2 4 2 5 3 4  最優應該為2個考場 即1，2不在一個考場。
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 1; i <=n ; i++) {
            Arrays.fill(vis[i],false);
            Arrays.fill(que[i],-1);
        }
        for(int i=0;i        {
            a=sc.nextInt();
            b=sc.nextInt();
            vis[a][b]=true;//鄰接矩陣，離散數學，用矩陣記錄關係
            vis[b][a]=true;
        }
        dfs(1,0);//開了
        System.out.println(ans);
    }
}

/<code>

閱讀更多 小白學習日記yang 的文章

關鍵字: 掃描儀 考場