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