#include<iostream> #include<cstring> #include<ctime> using namespace std; #define memoryMB(x) (sizeof(x)>>20) #define timeMS (clock()*1000/CLOCKS_PER_SEC) const int N=17,inf=0x3f3f3f3f; int g[N][N]; int F[1<<N],G[1<<N][N][N][2]; int n,lim; int sum; void init(){ cin>>n; for(int i=0;i<n;i++){ for(int j=0;j<n;j++)cin>>g[i][j]; } for(int i=0;i<n;i++){ for(int j=0;j<i;j++)if(g[i][j]>=0){ int m=min(g[i][j],g[j][i]); sum+=m; g[i][j]-=m; g[j][i]-=m; } } lim=(1<<n); } signed main(){ freopen("read.in","r",stdin); init(); cout<<sum; return 0; memset(F,0x3f,sizeof(F)); memset(G,0x3f,sizeof(G)); for(int i=0;i<n;i++)F[1<<i]=0; for(int s=1;s<lim;s++)if(F[s]<inf){ for(int i=0;i<n;i++)if((s>>i)&1)F[s]=min(F[s],G[s][i][i][1]); for(int i=0;i<n;i++)if((s>>i)&1){ for(int j=0;j<n;j++)if((s>>i)&1){ G[s][i][j][0]=min(G[s][i][j][0],F[s]); for(int k=0;k<=n;k++)if(g[i][k]>=0){ if(k==j){ G[s][k][j][1]=min(G[s][k][j][1],G[s][i][j][1]); } } } } } cerr<<memoryMB(F)+memoryMB(G)<<'\n'; cerr<<timeMS; return 0; }