1 /**************************************************************  2     Problem: 2039  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:5984 ms  7     Memory:64264 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 typedef long long ll; 16 const int N = 1005; 17 const int M = 4 * N * (N + 5); 18 const ll inf = (ll) 1e60; 19   20 struct edge { 21   int next, to; 22   ll f; 23   edge() {} 24   edge(int _n, int _t, ll _f) : next(_n), to(_t), f(_f) {} 25 } e[M]; 26   27 int n, S, T; 28 int first[N], tot = 1; 29 ll ans, a[N]; 30 int q[N], d[N]; 31   32 int read() { 33   int x = 0; 34   char ch = getchar(); 35   while (ch < ‘0‘ || ‘9‘ < ch) 36     ch = getchar(); 37   while (‘0‘ <= ch && ch <= ‘9‘) 38     (x *= 10) += ch - ‘0‘, ch = getchar(); 39   return x; 40 } 41   42 inline void add_edges(int x, int y, ll z) { 43   e[++tot] = edge(first[x], y, z), first[x] = tot; 44   e[++tot] = edge(first[y], x, 0), first[y] = tot; 45 } 46   47 inline void Add_Edges(int x, int y, int z) { 48   add_edges(x, y, z); 49   add_edges(y, x, z); 50 } 51   52 #define y e[x].to 53 #define p q[l] 54 bool bfs() { 55   int l, r, x; 56   memset(d, -1, sizeof(d)); 57   d[q[1] = S] = 1; 58   for (l = r = 1; l != r + 1; ++l) 59     for (x = first[p]; x; x = e[x].next) 60       if (!~d[y] && e[x].f) { 61     d[q[++r] = y] = d[p] + 1; 62     if (y == T) return 1; 63       } 64   return 0; 65 } 66 #undef p 67   68 ll dfs(int p, ll lim) { 69   if (p == T || !lim) return lim; 70   int x; 71   ll tmp, rest = lim; 72   for (x = first[p]; x && rest; x = e[x].next)  73     if (d[y] == d[p] + 1 && ((tmp = min(e[x].f, rest)) > 0)) { 74       rest -= (tmp = dfs(y, tmp)); 75       e[x].f -= tmp, e[x ^ 1].f += tmp; 76       if (!rest) return lim; 77     } 78   if (rest) d[p] = -1; 79   return lim - rest; 80 } 81 #undef y 82   83 ll Dinic() { 84   ll res = 0; 85   while (bfs()) 86     res += dfs(S, inf); 87   return res; 88 } 89   90 int main() { 91   int i, j, E; 92   n = read(); 93   S = n + 1, T = n + 2; 94   for (i = 1; i <= n; ++i) 95     add_edges(i, T, read()); 96   for (i = 1; i <= n; ++i) 97     for (j = 1; j <= n; ++j) { 98       ans += (E = read()); 99       if (i < j) {100     a[i] += E, a[j] += E;101     Add_Edges(i, j, (ll) E << 1);102       }103     }104   for (i = 1; i <= n; ++i)105     add_edges(S, i, a[i]);106   printf("%lld\n", ans - Dinic());107   return 0;108 }