1348 问题 B: 工作分配问题之剪枝函数

时间限制: 1s 内存限制: 128MB 提交: 9 解决: 8
题目描述

原来的工作分配问题，限时为10秒，所以不剪枝也能AC，本题的工作分配要求还是一样，但限时要求为1秒，所以本题要求用到剪枝函数。
剪枝函数的初步思路，就是在回溯搜索过程中，如果当前成本超过了已经搜索到的分配方案的成本，那么就这个分枝就没有搜索的意义，应该剪去。
稍微深入的想法是，就算当前费用小于已经搜索到的分配方案的费用，难道就一定有搜索的价值吗？也是未必，毕竟当前费用只包含了前面几项工作分配的所需费用，如果加上后面剩余工作的分配费用，那么就很可能超过已经搜索到的分配方案的费用。那么，如何估算剩余工作的分配费用？，每项工作，都可以算出最少费用，每项剩余工作的最少费用之和，是剩余工作的分配费用的下限。当前成本加上每项剩余工作的最少费用之和，应该小于已经搜索到的分配方案的费用。
本题要求按照这种深入的想法，去编写剪枝函数bound，以提高搜索的效率。

输入

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

输出

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

样例输入
3
10 2 3
3 3 4
3 4 5
样例输出
9
提示
无

                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
回溯法基础练习,第1题可以不剪枝，第2题必须剪枝。，希望都练习一下
                        

                    

                

                

                    

                        
比赛状况