SSOJ2369工作分配问题
5202+
作者: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行,当前的费用已经不低于最优费用了,那么后面再怎么分配工作都不会更好。