有一个由N*N个非负整数组成的方阵数组,现在规定每一行每一列只能取其中一个数,求所取的N个数的和的最小值。

输入:
第一行输入正整数N构建一个N*N的方阵
接下来有N行每行输入N个非负整数构建一个N*N的方阵

输出：输出其最小值的和。

输入:

4
1 3 5 7
1 1 3 5
3 1 1 3
5 3 1 1

输出:
4

3
1 3 4
2 2 3
3 1 2

输出:
5

虽然题目只要求计算结果，但最好按行坐标来打印出其中一种最小值的取法，例如第一个案例的取法是(1,1),(2,2),(3,3),(4,4)
第二个案例有两种取法~其中一种是(1,1),(2,2),(3,3)另外一种是(1,1),(2,3),(3,2)打印其中一种就行了~

现在除了想到全组合硬来外想不到其它更好的算法~求优化啊~

一楼说错了~应该是全排列~天哪~看来穷举法不太现实耶~

好吧~谢啦~

感觉证明其最小值还是很有难度啊~很久没有遭到如此卡壳的题目了~连个除了穷举外的实现思路都没有~

[此贴子已经被作者于2017-4-17 13:45编辑过]

我用C-Free运行了一下发现有不支持的地方
 error: `copy_n' was not declared in this scope
 error: `iota' was not declared in this scope

想到了如果当前解如果为最优解则无论交换任意两个取法的值都会比原来的要大~此时就可以结束循环了~不一定要算所有排列~
如果这条题实在优化不了就用全排列思路吧~

全排列穷举不难~难在优化~
想到了一些优化方法~就是当是最优解时无论交换任意两个数的和都会增大~这样判断次是数不稳定的~

一个数变换最小值状态可以考虑每次对齐一个数位这样最多交换N-1次~应该尽量避免交换过程中同一个数出现在相同的位置~想到了用逐步趋近最优状态的方法来求这个最小值~这和广搜有点关系……但算法复杂度似乎很高~而且这个方法的可行性还没有很大把握~

任意交换两个数最优解的和都会增大这个没啥好证明的~但现在纠结的是它的逆命题~任意交换两个数其和都会增大的必然是最优解~这个命题是否成立~~~

这个我有时间看看怎么去更新~先谢过啦~

其实这问题是一道灾区物资分配问题所引申出来的

假设现在在xoy坐标系里面有N个灾区，现在需要通过空投N个物资到该地区。但由于受天气和原因其它引起误差的因素物资降落地点会和期望降落到的灾区地点不同。物资通过空投降落后现在要尽量减少物资移动的总路线来重新把该物资分配到各个灾区。
第一行输入一个正整数N
接下来输入2*N行每一行包括两个浮点数，第一个是横坐标，第二个是纵坐标，中间用空格隔开
前面N行输入灾区坐标
后面N行输入实际救援物资的降落坐标

输出1行:救援物资重新分配到灾区移动的最小距离(结构保留两位小数)

示例:

输入:
3
1 1
2 1
3 3
1 2
3 2
2 3

输出：
3.41

感觉解决这个问题要对整体布局进行分析~
可以得出的信息就是各个灾区到各个救援物资之间的距离~

研究了一下解决方案就是要解决1楼的问题~一楼已经把这个实际问题简化了~

说个题外话~自己想看看那些动态规划以及其它类型的问题,发现一些高级一点的要用到高数知识例如线性代数~其中又看到欧拉函数啦表示一面懵逼~
所以感觉自己遇到真正上档次的题目发现自己还是很渺小啊~~

谢啦~先拿你的代码研究研究~

先谢过了~
好像输出和计算还是出了点问题,这个案例答案应该是9再看看~

谢各位回复了~现在不得不去上课~回来再对提供的代码进行深度测试~先谢过了~