[藍(lán)橋杯 2017 國(guó) C] 分考場(chǎng)(假題：最小色數(shù))

題目描述

$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\le a,b\le n)$ 表示第 $a$ 個(gè)人與第 $b$ 個(gè)人認(rèn)識(shí)（編號(hào)從 $1$ 開始）。

輸出格式

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

樣例 #1

樣例輸入 #1

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

樣例輸出 #1

4

樣例 #2

樣例輸入 #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í)限 1 秒, 256M。藍(lán)橋杯 2017 年第八屆國(guó)賽

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200;
int st[N][N];
int mp[N][N];//第i個(gè)考場(chǎng)的第i位同學(xué)
int n,m;
int minkey;
void dfs(int k,int res)//第k個(gè)同學(xué)，存在res個(gè)考場(chǎng)
{if(res>=minkey)return;//目前的考場(chǎng)數(shù)大于了最優(yōu)考場(chǎng)數(shù)，不再繼續(xù)if(k>n)//目前遍歷的是n+1位同學(xué)，沒有，已經(jīng)遍歷完了{minkey=min(minkey,res);//更新考場(chǎng)數(shù)return ;}for(int i=1;i<=res;i++)//依次遍歷每個(gè)考場(chǎng)，看有沒有認(rèn)識(shí)他的{int u=1;while(mp[i][u]&&!st[k][mp[i][u]])//如果第i個(gè)考場(chǎng)的第u名同學(xué)存在且不認(rèn)識(shí)，繼續(xù)往后遍歷u++;//注意這個(gè)u如果每個(gè)人都不認(rèn)識(shí)的話，這個(gè)u代表的是本考場(chǎng)人數(shù)加一//那么這個(gè)考場(chǎng)就沒有第u個(gè)人,if(!mp[i][u])//沒有第u個(gè)，讓第k個(gè)同學(xué)成為第u個(gè){mp[i][u]=k;dfs(k+1,res);mp[i][u]=0;//回溯}}//自己新加一個(gè)考場(chǎng)mp[res+1][1]=k;dfs(k+1,res+1);mp[res+1][1]=0;
}
int main()
{cin>>n>>m;minkey=n;while(m--){int a,b;cin>>a>>b;st[a][b]=1;//表示ab認(rèn)識(shí)st[b][a]=1;}dfs(1,0);//第1個(gè)同學(xué)有0個(gè)考場(chǎng)cout<<minkey;return 0;
}