#include #define For(i,a,b) for(int i=(a);i<=(b);++i) #define Rep(i,a,b) for(int i=(a);i>=(b);--i) using namespace std; inline int read() { char c=getchar();int x=0;bool f=0; for(;!isdigit(c);c=getchar())f^=!(c^45); for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48); if(f)x=-x;return x; } #define fi first #define se second #define pb push_back #define mkp make_pair typedef pairpii; typedef vectorvi; #define maxn 4000005 #define inf 0x3f3f3f3f #define N 805 int n,m; struct edge{ int u,v,w; }e[N][N]; int lab[N],sl[N],q[N],hd,tl,rt[N],col[N],mat[N],frm[N][N],fa[N]; int vis[N],tim; vi p[N]; int d(edge x){return lab[x.u]+lab[x.v]-e[x.u][x.v].w*2;} void upd(int u,int v){if(!sl[v]||d(e[u][v])0 && rt[i]!=u && col[rt[i]]==0) upd(i,u); } void push(int u){ if(u<=n) q[++tl]=u; else for(int x:p[u]) push(x); } void setrt(int u,int r){ rt[u]=r; if(u>n) for(int x:p[u]) setrt(x,r); } int rot(int b,int x){ int pos=find(p[b].begin(),p[b].end(),x)-p[b].begin(); if(pos%2==0)return pos; reverse(p[b].begin()+1,p[b].end()); return p[b].size()-pos; } void match(int u,int v){ mat[u]=e[u][v].v; if(u<=n)return; auto w=e[u][v]; int x=frm[u][w.u],pos=rot(u,x); For(i,0,pos-1) match(p[u][i],p[u][i^1]); match(x,v); rotate(p[u].begin(),p[u].begin()+pos,p[u].end()); } void aug(int u,int v){ assert(u&&v); int t=rt[mat[u]]; match(u,v); if(t) match(t,rt[fa[t]]),aug(rt[fa[t]],t); } int lca(int u,int v){ ++tim; while(u||v){ if(vis[u]==tim)return u; vis[u]=tim; u=rt[mat[u]]; if(u)u=rt[fa[u]]; if(!u)swap(u,v); }return 0; } int newn(){ int x=n+1; while(x<=m&&rt[x])++x; if(x>m)++m; p[x].clear(),lab[x]=mat[x]=rt[x]=col[x]=0; return x; } void blossom(int u,int v,int r){ int x=newn(); mat[x]=mat[r]; p[x].pb(r); for(int i=u;i!=r;i=rt[fa[i]]){ p[x].pb(i),p[x].pb(i=rt[mat[i]]); push(i); } reverse(p[x].begin()+1,p[x].end()); for(int i=v;i!=r;i=rt[fa[i]]){ p[x].pb(i),p[x].pb(i=rt[mat[i]]); push(i); } setrt(x,x); For(i,1,m)e[x][i].w=e[i][x].w=0,frm[x][i]=0; for(int t:p[x]){ For(i,1,m){ if(!e[x][i].w||d(e[t][i])0&&rt[u]!=rt[v]){ if(d(e[u][v])) upd(u,rt[v]); else if(path(e[u][v])) return 1; } } int tmp=inf; For(i,1,n) if(col[rt[i]]==0) tmp=min(tmp,lab[i]); For(i,n+1,m) if(rt[i]==i && col[i]==1) tmp=min(tmp,lab[i]>>1); For(i,1,m) if(rt[i]==i && sl[i] && col[i]!=1) tmp=min(tmp,d(e[sl[i]][i])>>(col[i]+1)); For(i,1,n){ if(col[rt[i]]==0) lab[i]-=tmp; if(col[rt[i]]==1) lab[i]+=tmp; if(lab[i]<=0) return 0; } For(i,n+1,m){ if(rt[i]==i){ if(col[i]==0) lab[i]+=tmp*2; if(col[i]==1) lab[i]-=tmp*2; } } hd=1,tl=0; For(i,1,m) if(rt[i]==i && sl[i] && rt[sl[i]]!=i && !d(e[sl[i]][i]) && path(e[sl[i]][i])) return 1; For(i,n+1,m) if(rt[i]==i && col[i]==1 && !lab[i]) expand(i); } } signed main(){ // freopen("group.in", "r", stdin); // freopen("group.out", "w", stdout); n=read(),m=n; int mx=0; For(i,1,n){ For(j,1,n){ int x = read(); e[i][j] = (edge){i, j, x}; frm[i][j] = 0; mx = max(mx, x); } } For(i,1,n)frm[i][i]=i; For(i,1,n)lab[i]=mx,rt[i]=i,p[i].clear(); while(bfs()); long long res=0; For(i,1,n)if(mat[i]&&i