1 #include <queue>  2 #include <cstdio>  3 #include <cstring>  4 #include <iostream>  5 #define N 1000001  6 #define min(x, y) ((x) < (y) ? (x) : (y))  7   8 int n, cnt, s, t;  9 int a[101][101], dis[N], pre[N]; 10 int head[N], to[N << 1], val[N << 1], cost[N << 1], next[N << 1]; 11 bool vis[N]; 12  13 inline int read() 14 { 15     int x = 0, f = 1; 16     char ch = getchar(); 17     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; 18     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; 19     return x * f; 20 } 21  22 inline void add(int x, int y, int z, int c) 23 { 24     to[cnt] = y; 25     val[cnt] = z; 26     cost[cnt] = c; 27     next[cnt] = head[x]; 28     head[x] = cnt++; 29 } 30  31 inline bool spfa() 32 { 33     int i, u, v; 34     std::queue <int> q; 35     memset(vis, 0, sizeof(vis)); 36     memset(pre, -1, sizeof(pre)); 37     memset(dis, 127 / 3, sizeof(dis)); 38     q.push(s); 39     dis[s] = 0; 40     while(!q.empty()) 41     { 42         u = q.front(), q.pop(); 43         vis[u] = 0; 44         for(i = head[u]; i ^ -1; i = next[i]) 45         { 46             v = to[i]; 47             if(val[i] && dis[v] > dis[u] + cost[i]) 48             { 49                 dis[v] = dis[u] + cost[i]; 50                 pre[v] = i; 51                 if(!vis[v]) 52                 { 53                     q.push(v); 54                     vis[v] = 1; 55                 } 56             } 57         } 58     } 59     return pre[t] ^ -1; 60 } 61  62 inline int dinic() 63 { 64     int i, d, sum = 0; 65     while(spfa()) 66     { 67         d = 1e9; 68         for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) d = min(d, val[i]); 69         for(i = pre[t]; i ^ -1; i = pre[to[i ^ 1]]) 70         { 71             val[i] -= d; 72             val[i ^ 1] += d; 73         } 74         sum += dis[t] * d; 75     } 76     return sum; 77 } 78  79 int main() 80 { 81     int i, j, x; 82     n = read(); 83     s = 0, t = n + n + 1; 84     memset(head, -1, sizeof(head)); 85     for(i = 1; i <= n; i++) 86     { 87         add(s, i, 1, 0); 88         add(i, s, 0, 0); 89         add(i + n, t, 1, 0); 90         add(t, i + n, 0, 0); 91         for(j = 1; j <= n; j++) 92         { 93             a[i][j] = read(); 94             add(i, j + n, 1, a[i][j]); 95             add(j + n, i, 0, -a[i][j]); 96         } 97     } 98     printf("%d\n", dinic()); 99     cnt = 0;100     memset(head, -1, sizeof(head));101     for(i = 1; i <= n; i++)102     {103         add(s, i, 1, 0);104         add(i, s, 0, 0);105         add(i + n, t, 1, 0);106         add(t, i + n, 0, 0);107         for(j = 1; j <= n; j++)108         {109             add(i, j + n, 1, -a[i][j]);110             add(j + n, i, 0, a[i][j]);111         }112     }113     printf("%d\n", -dinic());114     return 0;115 }