站外题求助!
  • 板块学术版
  • 楼主youzhigui_nie
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/2/2 20:00
  • 上次更新2023/10/24 02:00:18
查看原帖
站外题求助!
756163
youzhigui_nie楼主2023/2/2 20:00

题目如下:

设有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; 
}

为何会死循环?

2023/2/2 20:00
加载中...