工作分配问题(c++题解)

题目描述设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法为每一个人都 分配一件不同的工作并使总费用达到最小。设计一个算法对于给定的工作费用计算最佳工作分配方案使总费用达到最小。输入格式由文件job.in给出输入数据。第一行有1个正整数n (1≤n≤20)。接下来的n行每行n个数第i行表 示第i个人各项工作费用。输出格式输出最小总费用样例样例输入复制3 4 2 5 2 3 6 3 4 5样例输出复制9_____________________________________________________________________________写作不易点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!_____________________________________________________________________________#includebits/stdc.h using namespace std; int n,m,ansINT_MAX; int a[25][25]; bool b[25]; void dfs(int h,int cnt){ if(cntans)return; if(hn1){ ansmin(cnt,ans); return; } for(int i1;in;i){ if(b[i])continue; b[i]true; dfs(h1,cnta[h][i]); b[i]false; } } int main(){ cinn; for(int i1;in;i){ for(int j1;jn;j){ cina[i][j]; } } dfs(1,0); coutans; }