2018年1月月赛工作分配问题题解

题目描述

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

输入输出格式

输入格式

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

输出格式

一行，包含一个正整数，为计算出的最小总费用。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于100%的数据，1<=n<=20，1<=c[i][j]<=100。

分析数据，发现最大数据为所有c[i][j]的和。而格子数最大只有n*n=400，每个c[i][j]最大只有100，故最大数据不大于40000，可以采用int类型。

本题也有网络流解法，但网络流解法思维难度过大，不予讨论。

采用dfs解决本问题。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
bool v[30]={false};
long long ans=0;
int c[30][30],n;
void dfs(int x,int sum)
{
    if(x>n)
    {
        if(sum<ans) ans=sum;
        return;
    }
    if(ans>sum)
    {
        for(int i=1;i<=n;i++)
        {
            if(!v[i])
            {
                v[i]=true;
                dfs(x+1,sum+c[x][i]);
                v[i]=false;
            }
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>c[i][j];
            ans+=c[i][j];
        }
    }
    dfs(1,0);
    cout<<ans;
    return 0;
}

采用ans先存储所有c[i][j]的和，这里也可以将ans初始化为一个远大于40000的值。

用v数组保存工作分配情况，v[i]=true表示第i件工作已经被分配，v[i]=false表示第i件工作未被分配。

用dfs函数来执行深搜。dfs函数带有两个参量，其中x表示现在正在被分配工作的人的编号，sum表示目前总花费。

当x>n时表示人已经被枚举完了，此时判断sum是否小于已有答案ans，若是，则表示产生了更优解，更新ans的值。

如果数据简单的话，到这里就可以过了。但本题数据较为复杂，需要剪枝。

不论当前枚举到第几个人，只要当前sum>=ans，就表示最终的sum不会比ans小，不会产生更优的解答。所以当且仅当ans>sum的时候继续递归。