SSOJ2369工作分配问题
5477+
作者：crxis 发布：2017-07-28 分类：深度优先搜索
题目大意：有n件工作分配给n个人，将工作i分配给第j个人所需的费用为cij，每个人分配一件工作，最小费用是多少？
题目描述
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法，为每一个人都分配一件不同的工作，并使总费用达到最小。
设计一个算法，对于给定的工作费用，计算最佳工作分配方案，使总费用达到最小。
输入
输入共两行，第一行有一个正整数n(1<=n<=20)。接下来的n行，每行n个数，第i行表示第i个人各项工作费用。
输出
输出最小总费用
样例输入
3
4 2 5
2 3 6
3 4 5
样例输出
9
解题思路
格子填数类型的搜索题目，时间复杂度一般都是阶乘级别或者n次方级别的，数据量大了，不优化就会超时。
这里介绍两种优化方法：一是可行性剪枝，如果可行，我才继续搜索，如第9行，没分配过的工作才分配，重复分配是不可行的；二是最优性剪枝，算出来的结果比之前得到的更差，就不继续搜索，如第5行，当前的费用已经不低于最优费用了，那么后面再怎么分配工作都不会更好。
程序实现
