请教高手：n行n列的矩阵，从中选n个数，不同行不同列，并使其和最

n行n列的矩阵，从中选n个数，不同行不同列，并使其和最大。怎么做？
除了O（n!）的做法，大家能不能想到别的？

网络流

带权二分图匹配

不怕麻烦超时，你就回溯

这不是最佳匹配问题么？很经典的

其实就是二分图最优匹配，可以用km算法～

贴个代码，KM算法的，O(N^3)
#include<iostream> //O(n^3)的KM
using namespace std;
const int maxn=101;
const int inf= 10000000;
int tc;
int g[maxn][maxn], lx[maxn], ly[maxn], vx[maxn], vy[maxn], mat[maxn],slack[maxn];
int n;
bool find(int u)
{
vx[u] = 1;
for(int v=1; v<=n; v++)
{
if(!vy[v] && lx[u] + ly[v] == g[u][v])
{
vy[v] = 1;
if(mat[v] == -1 || find(mat[v]))
{
mat[v] = u;
return true;
}
}
else if(lx[u]+ly[v]>g[u][v])
slack[v]=min(slack[v],lx[u]+ly[v]-g[u][v]);
}
return false;
}
void km()
{
int d, sum;
memset(lx, 0, sizeof(lx));
memset(ly, 0, sizeof(ly));
memset(mat, -1, sizeof(mat));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
lx[i]=max(lx[i],g[i][j]);
}
}
for(int k=1; k<=n; k++)
{
while(1)
{
memset(vx, 0, sizeof(vx));
memset(vy, 0, sizeof(vy));
for(int i=1;i<=n;i++)
slack[i]=inf;
if(find(k))
break;
d = inf;
for(int i=1; i<=n; i++)
{
if(!vy[i])
{
d=min(d,slack[i]);
}
}
for(int i=1; i<=n; i++)
{
if(vx[i])
lx[i] -= d;
if(vy[i])
ly[i] += d;
}
}
}
sum = 0;
for(int i=1; i<=n; i++)
sum += lx[i] + ly[i];
printf("%d\n", sum);
}
int main()
{
while(scanf("%d",&n)&& n)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d",&g[i][j]);
}
}
km();
}
return 0;
}


目测编程之美的题目