1 /**************************************************************  2     Problem: 2597  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:11144 ms  7     Memory:10756 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13   14 using namespace std; 15 const int Num = 105; 16 const int N = Num * Num; 17 const int M = 500005; 18 const int inf = (int) 1e9; 19   20 struct edges { 21     int next, to, f, cost; 22     edges() {} 23     edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {} 24 } e[M]; 25    26 int tot = 1, first[N]; 27 int n, m, S, T; 28 int in[Num], d[N], q[N], g[N]; 29 int sum[M]; 30 bool v[N]; 31   32 inline 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 = x * 10 + ch - ‘0‘; 39         ch = getchar(); 40     } 41     return x; 42 } 43   44 inline void Add_Edges(int x, int y, int f, int c) { 45     e[++tot] = edges(first[x], y, f, c), first[x] = tot; 46     e[++tot] = edges(first[y], x, 0, -c), first[y] = tot; 47 } 48    49 inline int calc() { 50     int flow = inf, x; 51     for (x = g[T]; x; x = g[e[x ^ 1].to]) 52         flow = min(flow, e[x].f); 53     for (x = g[T]; x; x = g[e[x ^ 1].to]) 54         e[x].f -= flow, e[x ^ 1].f += flow; 55     return flow; 56 } 57    58 bool spfa() { 59     int x, y, l, r; 60     for (x = 1; x <= T; ++x) 61         d[x] = inf; 62     d[S] = 0, v[S] = 1, q[0] = S; 63     for(l = r = 0; l != (r + 1) % N; ++l %= N) { 64         for (x = first[q[l]]; x; x = e[x].next) 65             if (d[q[l]] + e[x].cost < d[y = e[x].to] && e[x].f) { 66                 d[y] = d[q[l]] + e[x].cost, g[y] = x; 67                 if (!v[y]) 68                     q[++r %= N] = y, v[y] = 1; 69             } 70         v[q[l]] = 0; 71     } 72     return d[T] != inf; 73 } 74   75 inline int work() { 76     int res = 0; 77     while (spfa()) 78         res += calc() * d[T]; 79     return res; 80 } 81   82 void build_graph() { 83     int i, j, x, now = 0; 84     for (i = 1; i <= n; ++i) 85         for (j = 1; j <= n; ++j) { 86             x = read(); 87             if (j <= i) continue; 88             sum[++now] = i + j; 89             if (x == 2) { 90                 Add_Edges(now, i + m, 1, 0), Add_Edges(now, j + m, 1, 0); 91                 ++in[i], ++in[j]; 92             } else 93             if (x == 1) Add_Edges(now, i + m, 1, 0), ++in[i]; 94             else Add_Edges(now, j + m, 1, 0), ++in[j]; 95         } 96     for (i = 1; i <= m; ++i) 97         Add_Edges(S, i, 1, 0); 98     for (i = 1; i <= n; ++i) 99         for (j = 1; j <= in[i]; ++j)100             Add_Edges(i + m, T, 1, 2 * j - 1);101 }102  103 void make_ans() {104     int a[Num][Num], i, j, x;105     memset(a, 0, sizeof(a));106     for (i = 1; i <= m; ++i)107         for (x = first[i]; x; x = e[x].next)108             if (!e[x].f) a[e[x].to - m][sum[i] - e[x].to + m] = 1;109     for (i = 1; i <= n; ++i) {110         for (j = 1; j <= n; ++j)111             printf("%d ", a[i][j]);112         printf("\n");113     }114 }115  116 int main() {117     n = read(), m = n * (n - 1) / 2;118     S = n + m + 1, T = S + 1;119     build_graph();120     printf("%d\n", (n * (n - 1) * (n - 2) / 3 + m - work()) / 2);121     make_ans();122     return 0;123 }