1 /*--------------------------------------------------------------------------------------*/  2   3 #include <algorithm>  4 #include <iostream>  5 #include <cstring>  6 #include <ctype.h>  7 #include <cstdlib>  8 #include <cstdio>  9 #include <vector> 10 #include <string> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <set> 15 #include <map> 16  17 //debug function for a N*M array 18 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");} 21 //debug function for int,float,double,etc. 22 #define debug_var(X) cout<<#X"="<<X<<endl; 23 #define LL long long 24 const int INF = 0x3f3f3f3f; 25 const LL LLINF = 0x3f3f3f3f3f3f3f3f; 26 /*--------------------------------------------------------------------------------------*/ 27 using namespace std; 28  29 int N,M,T; 30 const int maxn = 310; 31 int nx,ny; 32 int g[maxn][maxn]; 33 int linker[maxn],lx[maxn],ly[maxn]; 34 int slack[maxn]; 35 bool visx[maxn],visy[maxn]; 36 bool DFS(int x) 37 { 38     visx[x] = true; 39     for(int y=0;y<ny;y++) 40     { 41         if(visy[y]) continue; 42         int tmp = lx[x] + ly[y] - g[x][y]; 43         if(tmp == 0) 44         { 45             visy[y] = true; 46             if(linker[y] == -1 || DFS(linker[y])) 47             { 48                 linker[y] = x; 49                 return true; 50             } 51         } 52         else if(slack[y] > tmp) slack[y] = tmp; 53     } 54     return false; 55 } 56 int KM() 57 { 58     memset(linker,-1,sizeof linker); 59     memset(ly,0,sizeof ly); 60     for(int i=0;i<nx;i++) 61     { 62         lx[i] = -INF; 63         for(int j=0;j<ny;j++)   lx[i] = max(lx[i],g[i][j]); 64     } 65     for(int x=0;x<nx;x++) 66     { 67         for(int i=0;i<ny;i++) slack[i] = INF; 68         while(true) 69         { 70             memset(visx,false,sizeof visx); 71             memset(visy,false,sizeof visy); 72             if(DFS(x)) break; 73             int d = INF; 74             for(int i=0;i<ny;i++) if(!visy[i] && d > slack[i]) d = slack[i]; 75             for(int i=0;i<nx;i++) if(visx[i]) lx[i] -= d; 76             for(int i=0;i<ny;i++) 77             { 78                 if(visy[i]) ly[i] += d; 79                 else slack[i] -= d; 80             } 81         } 82     } 83     int res = 0; 84     for(int i=0;i<ny;i++) if(linker[i] != -1) res += g[linker[i]][i]; 85     return res; 86 } 87 int main() 88 { 89     while(~scanf("%d",&N)) 90     { 91         for(int i=0;i<N;i++) 92         { 93             for(int j=0;j<N;j++) 94             { 95                 scanf("%d",&g[i][j]); 96             } 97         } 98         nx = ny = N; 99         printf("%d\n",KM());100     }101 }