站外题,求调玄关
  • 板块灌水区
  • 楼主MAX_CURRY_JAMES
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/22 08:53
  • 上次更新2025/1/22 11:12:04
查看原帖
站外题,求调玄关
796776
MAX_CURRY_JAMES楼主2025/1/22 08:53

题目:

描述

设有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怎么超

2025/1/22 08:53
加载中...