题目:
描述
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法,为每一个人都分配一件不同的工作,并使总费用达到最小。
输入
第一行有一个正整数n(1<=n<=20)。接下来的n行,每行有n个数,第i行表示第i个人各项工作费用。
输出
输出计算出的最小总费用。
输入格式 无
输出格式 无
输入/输出例子1 输入:
3
4 2 5
2 3 6
3 4 5
输出:
9
代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[25][25],b[25],c[25],zx=0x3f3f3f3f3f,sum;
void dfs(int t) {
if (t==n) {
sum=0;
for (int i=1;i<=n;i++)
sum+=a[i][c[i]];
zx=min(zx,sum);
return;
}
for (int i=1;i<=n;i++)
if (b[i]==0) {
b[i]=1,c[t+1]=i;
dfs(t+1);
b[i]=0;
}
}
signed main() {
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(0);
printf("%d",zx);
return 0;
}
两个点超时,想不明白你<=20怎么超