仕事の分配~問題解(c++)——【S神】蘇嘉億
Description 2020年、手紙は自分でN人の従業員を持つ大手会社を設立した.毎日、手紙はN項目の仕事を彼の従業員に割り当てなければならないが、能力の違いで、一人一人が同じ仕事を処理するのに必要な時間が速くて遅い.周知のように、手紙は効率を非常に重視する人で、彼はどのように仕事を分配してこそ、すべての仕事を完成する時間の合計を最小限に抑えることができるかを知りたいと思っています(従業員は1つの仕事にしか割り当てられません).しかし、私たちも手紙が普通の怠け者ではないことを知っています.だから、手紙はあなたを見つけました.手紙を救ってください.
Inputの最初の行には、1からNまでの従業員番号を持つN個の従業員を表す整数Nが入力されます.(1≦N≦10)次にN*Nの2次元マトリクスtask[N][N]を入力し、task[i][j]はi番目の作業がj番の従業員によって完了するのに要する時間を指す.(0 ≤ task[i][j] ≤ 1000)
Output出力結果には、必要最小限の時間(合計)を表す整数が含まれます.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Hintサンプルの場合、1番目のタスクは5番の従業員で完了し、2番目のタスクは2番の従業員で完了し、3番目のタスクは4番の従業員で完了し、4番目のタスクは1番の従業員で完了し、5番目のタスクは3番の従業員で完了し、6番目のタスクは6番の従業員で完了し、合計時間9+9+10+9+8=54を費やします.
コード#コード#
Inputの最初の行には、1からNまでの従業員番号を持つN個の従業員を表す整数Nが入力されます.(1≦N≦10)次にN*Nの2次元マトリクスtask[N][N]を入力し、task[i][j]はi番目の作業がj番の従業員によって完了するのに要する時間を指す.(0 ≤ task[i][j] ≤ 1000)
Output出力結果には、必要最小限の時間(合計)を表す整数が含まれます.
Sample Input 1
3
4 2 5
2 3 6
3 4 5
Sample Output 1
9
Sample Input 2
6
10 11 12 11 9 11
11 9 10 13 11 12
12 10 11 10 13 9
9 14 9 10 10 11
10 10 9 11 12 11
10 7 10 10 10 8
Sample Output 2
54
Hintサンプルの場合、1番目のタスクは5番の従業員で完了し、2番目のタスクは2番の従業員で完了し、3番目のタスクは4番の従業員で完了し、4番目のタスクは1番の従業員で完了し、5番目のタスクは3番の従業員で完了し、6番目のタスクは6番の従業員で完了し、合計時間9+9+10+9+8=54を費やします.
コード#コード#
#include
using namespace std;
int vis[15];
int a[15][15];
int b[15];//b[i] i
int n,ans=1e9;
void dfs(int t){
if(t>n){
int sum=0;
for(int i=1;i<=n;i++){
sum+=a[i][b[i]];
}
ans=min(ans,sum);//
return;
}//
for(int i=1;i<=n;i++){
if(!vis[i]){
b[t]=i;// i t
vis[i]=1;//
dfs(t+1);// ,
vis[i]=0;//
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
dfs(1);//
printf("%d",ans);
return 0;
}