有一个由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:40编辑过]

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

好吧~谢啦~

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

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

就是一个“全排列”算法，以3*3为例
0,1,2的全排列有 {0,1,2}, {0,2,1}, {1,0,2}, {1,2,0}, {2,0,1}, {2,1,0}
举例 {1,2,0}，表示 arr[0][1]+arr[1][2]+arr[2][0]

用C++写就是：

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <numeric>
using namespace std;

int main( void )
{
    size_t n;
    cin >> n;
    vector<size_t> arr( n*n );
    copy_n( std::istream_iterator<size_t>(cin), n*n, arr.begin() );

    size_t min_sum = std::numeric_limits<size_t>::max();
    {
        vector<size_t> idx( n );
        iota( idx.begin(), idx.end(), 0 );
        do
        {
            size_t sum = 0;
            for( size_t r=0; r!=n; ++r )
                sum += arr[ r*n + idx[r] ];
            min_sum = min( min_sum, sum );
        }
        while( std::next_permutation(idx.begin(),idx.end()) );
    }
    cout << min_sum << endl;
}

楼上的算法在我的笔记本上计算10*10的矩阵需要大约1分钟。12*12的我试了一下，没耐心等所以换成了10*10

时间越来越长是肯定的，T(n)耗时是T(n-1)的n倍

我用gcc 6.3.0试了一下，
debug下：10*10耗时  0.909287秒；release下差不多
debug下：11*11耗时  9.702019秒；release下差不多
debug下：12*12耗时118.991265秒；release下差不多
我怀疑你用的编译器在debug下加了太多的调试信息。

算法是没优化（sum不需要从头开始计算），但即使优化，也不会有数量级的差距

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <numeric>
using namespace std;

#include <chrono>

int main( void )
{
    size_t n;
    cin >> n;
    vector<size_t> arr( n*n );
    copy_n( std::istream_iterator<size_t>(cin), n*n, arr.begin() );

std::chrono::time_point<std::chrono::steady_clock> now = std::chrono::steady_clock::now();

    size_t min_sum = std::numeric_limits<size_t>::max();
    {
        vector<size_t> idx( n );
        iota( idx.begin(), idx.end(), 0 );
        do
        {
            size_t sum = 0;
            for( size_t r=0; r!=n; ++r )
                sum += arr[ r*n + idx[r] ];
            min_sum = min( min_sum, sum );
        }
        while( std::next_permutation(idx.begin(),idx.end()) );
    }

std::chrono::time_point<std::chrono::steady_clock> cur = std::chrono::steady_clock::now();
std::cout << std::chrono::duration_cast<std::chrono::microseconds>(cur-now).count() << std::endl;

    cout << min_sum << endl;

}

我在powershell里面运行的，所以非常慢

错了，编辑掉

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

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

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

一回来就出道这么难的题。算法真不好设计

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

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