站外题，求调玄关

题目：

描述

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。

输入

第一行有一个正整数n（1<=n<=20)。接下来的n行，每行有n个数，第i行表示第i个人各项工作费用。

输出

输出计算出的最小总费用。

输入格式无

输出格式无

输入/输出例子1 输入：

4 2 5

2 3 6

3 4 5

输出：

代码：

CPP

#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怎么超

站外题，求调玄关

讨论操作

回复

相关推荐

站外题，求调玄关