题目如下:
设有m件工作分配给n个人。如果第i个人被分配到工作j所需费用为c[i][j]。请为每一个人都分配一件不同的工作,并使总费用达到最小。
输入格式 :第一行有2个正整数n, m(1≤n≤m≤20)。接下来的n行,每行m个数,第i行表示第i个人各项工作费用,数字不超过100000
输出格式 :输出一行,即最小总费用
代码如下:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int MAX=29;
int n,m;
int c[MAX][MAX],p[MAX];
int ans1=INF,ans;
void sum(){
for(int i=1;i<=m;i++) ans+=c[n][p[i]];
ans=min(ans,ans1);
ans1=ans;
}
void dfs(int x,int y){//当前候选列号为x已选了y个数
if(y==n){
sum();
return;
}
for(int i=x;i<=m+1-n+y;i++){//枚举第c+1个人的列号
p[y+1]=i;//选中为i
dfs(i+1,y+1);
}
}
int main(){
//freopen("work.in","r",stdin);
//freopen("work.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;i++)
cin>>c[i][j];
dfs(1,0);
cout<<ans;
return 0;
}
为何会死循环?