工作分布问题

正文索引 [隐藏]

题目描述：

设有n件工作分配给n个人，将工作i分配给第j个人所需的费用为

C_{ij}
。试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。

输入描述：

第1行有1个正整数n(1≤n≤20)，接下来的n行，每行有n个数表示工作费用。

输出描述：

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

输入样例：

3
10 2 3
2 3 4
3 4 5

输出样例：

9

解题思路：

回溯法。用minCost来记录最小总费用，将工作i分配给第j个人所需要的费用是c[i][j]，用vis数组来标记工作是否被分配。用traceback函数来进行回溯，第一个参数表示当前在给第i个人找工作，第二个参数cnt表示当前总花费。若当前花费小于最小总花费，则对所有工作岗位进行遍历，把空余的工作交给i。当所有人都分配到了工作时，比较当前总花费是否小于最小总花费，若小于则对最小总花费进行更新。最后输出最小总花费即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for (int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxn = 21;
int n,minCost = 0;
int c[maxn][maxn];     //将工作i分配给第j个人所需的费用为c[i][j]
bool vis[maxn];       //vis[i]用于标记第i个工作是否被分配
void traceback(int i,int cnt)   //回溯
{
    if(i>n && cnt<minCost)
    {
        minCost = cnt;
        return ;
    }
    if(cnt < minCost)
    {
        Up(j,1,n)
        {
            if(!vis[j])
            {
                vis[j] = true;
                traceback(i+1,cnt+c[i][j]);
                vis[j] = false;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(c,INF);
    ms(vis,false);
    cin >> n;
    Up(i,1,n)
    {
        Up(j,1,n)
        {
            cin >> c[i][j];
            minCost += c[i][j];
        }
    }
    traceback(1,0);
    cout << minCost << endl;
    return 0;
}
C++
Copy