#include<stdio.h> #include<queue> #include<string.h> using namespace std; #define inf 0x7fffffff struct node{ int u,v,w,f,next; }bian[20000]; int dis[6000],pre[6000],head[6000],visit[6000],yong,minf; void build(int u,int v,int w,int f) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].f=f; bian[yong].next=head[u]; head[u]=yong++; } void adde(int u,int v,int w,int f) { build(u,v,w,f); build(v,u,-w,0); } int spfa(int s,int t) { memset(visit,0,sizeof(visit)); memset(pre,-1,sizeof(pre)); for(int i=0;i<=t;i++)//注意是从0开始而不是从s开始 dis[i]=inf; queue<int>q; visit[s]=1;//必须是s q.push(s); dis[s]=0; while(!q.empty ()) { int u=q.front (); for(int index=head[u];index!=-1;index=bian[index].next) { int v=bian[index].v; if(bian[index].f&&dis[v]>dis[u]+bian[index].w) { dis[v]=dis[u]+bian[index].w; pre[v]=index; if(!visit[v]) { visit[v]=1; q.push (v); } } } q.pop(); visit[u]=0;//是u } if(dis[t]==inf) return 0; return 1; } void addf(int s,int t ) { int i=pre[t]; int j; while(i!=-1) { j=i^1; bian[i].f--; bian[j].f++; minf+=bian[i].w; i=pre[bian[i].u];//前一个u } } int main() { int n,k,map[60][60]; while(scanf("%d",&n)!=EOF) { memset(head,-1,sizeof(head)); k=2; yong=0; int s=2*n*n; int t=s+1; int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&map[i][j]); for(i=0;i<n;i++) for(j=0;j<n;j++) { int b=i*n+j; adde(2*b,2*b+1,-map[i][j],1); adde(2*b,2*b+1,0,k-1); } for(i=0;i<n;i++) for(j=0;j<n-1;j++) { int b=i*n+j; adde(2*b+1,2*(b+1),0,k); } for(i=0;i<n-1;i++) for(j=0;j<n;j++) { int b=i*n+j; adde(2*b+1,2*(b+n),0,k); } adde(s,0,0,k); adde(2*n*n-1,t,0,k); minf=0; while(spfa(s,t)) { addf(s,t); } printf("%d ",-minf); } return 0; }