题目描述

在工厂里，如果每道工序让不同的工人来做，所要花费的时间往往不一样。精明的老板为了提高效率，总是把生产某一产品所需要的N道工序进行最佳搭配，使生产某一产品所花费的总时间最少。现在就给出N个工人分别做N道工序所要花费的时间，请你来计算一下,如果N个工人每人做N道工序中其中的一道，那么生产某一产品（即完成所有N道工序）所要花费的最少时间是多少。

输入格式:
输入文件job.in的第1行有1个整数N(1≤N≤20)，表示有N个工人。接下来的N行，每行N个数，表示该工人完成各道工序所要花费的时间。

输出格式:
输出文件job.out共一行，即生产某一产品所要花费的最少时间。

输入样例:
4
1 3 2 4
3 2 4 5
3 4 1 2
4 5 3 2
输出样例:
6
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB

样例

4
1 3 2 4
3 2 4 5
3 4 1 2
4 5 3 2

6

算法1

(全排列和回溯剪枝) $O(n!)$

一道典型全排列进阶题，数据小，可循环枚举，但会部分超时，用剪枝即可满分。

时间复杂度

$O(n!)$

参考文献

要掌握全排列和递归函数

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,Min=INT_MAX;
int a[105],b[105][105];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        a[i]=i;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>b[i][j];
    do
    {
        int hang=1;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            sum+=b[hang][a[i]];
            if(sum>=Min) break;//回溯剪枝
            hang++;
        }
        Min=min(Min,sum);
    }while(next_permutation(a+1,a+1+n));//全排列
    cout<<Min;
}