我用状态压缩做的。
一个有少于18000的合格状态，再DP 就好。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define max(a,b) a>b?a:b;
int value[23][23];
int status[18000];
int dp[22][18000];
int n,top;
int sum(int c,int sts)
{
int val=0;
int i=0;
while(sts){
if(sts&1)
val+=value[c][n-1-i];
sts=sts>>1;
i++;
}
return val;
}
void Init()
{
int i;
top=0;
int total=1<<n;
for(i=0;i<total;i++){
if(i&(i<<1)) continue;
status[top++]=i;
}
}
bool fit(int a,int b)
{
if(a&b) return false;
return true;
}
void DP()
{
int i,j,k;
memset(dp,0,sizeof(dp));
for(i=0;i<top;i++){
dp[0][i]=sum(0,status[i]);
}
for(i=1;i<n;i++){
for(j=0;j<top;j++)
for(k=0;k<top;k++){
if(fit(status[j],status[k])){
int sum1=sum(i,status[j]);
dp[i][j]=max(dp[i][j],dp[i-1][k]+sum1);
}
}
}
int ans=dp[n-1][0];
for(i=0;i<top;i++)
ans=max(ans,dp[n-1][i]);
printf("%d\n",ans);
}
int main()
{
int i,j;
while(scanf("%d",&n)!=EOF){
if(n==0) {
printf("0\n");
continue;
}
Init();
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&value[i][j]);
DP();
}
return 0;
}