編程之美1.9 高效安排會(huì)議
一 問題描述：
已知有n位學(xué)生，他們分別對(duì)m個(gè)分組中的若干個(gè)感興趣。
每個(gè)學(xué)生都必須能夠參加，他們所感興趣的部門的會(huì)議。
每個(gè)會(huì)議的開會(huì)時(shí)間都為t，求會(huì)議如何安排使得需要的總時(shí)間最短。
其中一個(gè)最簡(jiǎn)單的方法：
即每個(gè)會(huì)議不會(huì)同時(shí)召開，則時(shí)間變?yōu)閙 * t。
二 問題分析：
下面我們需要尋找可以同時(shí)召開的會(huì)議，來進(jìn)一步減少花費(fèi)的總時(shí)間。
問題建模：
這個(gè)題目可以轉(zhuǎn)換為圖的最少著色問題：
(1)即將兩個(gè)不能同時(shí)召開的會(huì)議，用同一條直線進(jìn)行連接。
(2)然后對(duì)圖中的每個(gè)頂點(diǎn)進(jìn)行著色，保證有直線連接的兩個(gè)節(jié)點(diǎn)之間不允許重色。
(3)先隨意將其中一個(gè)節(jié)點(diǎn)染色，然后對(duì)剩余的n-1個(gè)節(jié)點(diǎn)，進(jìn)行n個(gè)顏色的枚舉，
復(fù)雜度為o((n-1)^n) 。
(4)著色之后，需要對(duì)每一個(gè)頂點(diǎn)進(jìn)行判斷，則復(fù)雜度為o(n*n)。
(5)則全部的時(shí)間復(fù)雜度為o((n-1)^n * o(n*n))
三代碼如下：
#include <iostream>
using namespace std ;
const int N = 3 ; //學(xué)生數(shù)目
const int M = 4 ; //會(huì)議的數(shù)目
int meet[N][M] = //表示每個(gè)學(xué)生感興趣的會(huì)議信息
{
{1 , 1 , 1 , 0} ,
{0 , 1 , 1 , 1} ,
{0 , 1 , 1 , 0} ,
} ;
int path[M][M] = //根據(jù)meet二維數(shù)組。建立起
{
{0 , 0 , 1 , 0} ,
{0 , 0 , 0 , 1} ,
{1 , 0 , 0 , 0} ,
{0 , 1 , 0 , 0}
} ;
int color[M] = {0 , -1 , -1 ,-1}; //初始化顏色數(shù)組，每一個(gè)頂點(diǎn)有一個(gè)顏色
bool judge(int i , int j)//判斷第i個(gè)節(jié)點(diǎn)，當(dāng)涂j顏色的時(shí)候，是否滿足
{
for(int w = 0 ; w < M ;w++)
{
if(path[i][w]) //若是i 和 w兩點(diǎn)相鄰，則需要判斷 兩者的顏色是否相同
{
if(color[i] == color[w])
return false ;
}
}
return true ;
}
int arrange()
{
int num = 0 ; //表示可以同時(shí)安排的會(huì)議的數(shù)目
for(int i = 1 ; i < M ;i++)//表示每一個(gè)頂點(diǎn)
{
for(int j = 0 ; j < M ;j++) //表示每一種顏色
{
color[i] = j ; //對(duì)應(yīng)節(jié)點(diǎn)設(shè)置為顏色j，設(shè)置完畢之后，判斷該顏色是否滿足
if(judge(i , j)) //判斷第i個(gè)節(jié)點(diǎn)，當(dāng)涂j顏色的時(shí)候，是否滿足
{
break;
}
}
}
for(int i = 0 ; i< M ;i++)
{
cout<<color[i]<<" " ;
if(num < color[i])
num = color[i] ;
}
return num + 1;
}
int main()
{
int time = 5 ; //每個(gè)會(huì)議持續(xù)的時(shí)間
int t = arrange() ;
cout<<"花費(fèi)總的時(shí)間:"<<time * t<<endl ;
getchar() ;
return 0 ;
}