Chaos Slover 补档计划 - 网络流相关题目与应用(3 费用流)

2015.11.26 10:48 Thu| 2 visits oi_2016| ChaosSlover补档计划| Text

HOJ2543 Stone IV

HOJ网站:http://acm.hit.edu.cn/hoj/problem/volume

这几天做了好多奇怪 OJ 上的题啊!

这道题建图很显然地,将一条边拆成有费用和无费用两条。然后多次找到最短路并做尽可能的增广。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

#define N 1005
#define M 80005
#define inf 0x3f3f3f3f

int test, n, m, c, p;
int s, t, head[N], cnt, v[N], d[N], from[N], inc[N];

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0, v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    if (d[t] == inf) return false;
    return true;
}

void update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m >> c >> p;
        s = n, t = 1;
        init();
        add(s, 0, inf, p), add(0, s, 0, -p);
        for (int u, v, c1, c2, i = 1; i <= m; ++i)
        {
            cin >> u >> v >> c1 >> c2;
            add(u, v, c1, 0), add(v, u, 0, 0);
            add(u, v, inf, c2), add(v, u, 0, -c2);
            add(v, u, c1, 0), add(u, v, 0, 0);
            add(v, u, inf, c2), add(u, v, 0, -c2);
        }
        long long sum = 0;
        int ans = 0;
        while (sum <= c)
        {
            spfa(); update();
            if (sum + 1ll * d[t] * inc[t] <= c)
                ans += inc[t], sum += 1ll * d[t] * inc[t];
            else
                { ans += (c - sum) / d[t]; break; }
        }
        cout << ans << endl;
    }
    return 0;
}

HOJ2715 Matrix3

天哪!费用流的建图真的不知道比那些最大流麻烦到哪里去了。

这道题目里面存在高度的限制,从而不会出现负权环。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;

#define N 6005
#define M 80005
#define inf 0x3f3f3f3f

int test, n, k, h[55][55];
int s, t, head[N], cnt, v[N], d[N], from[N], inc[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0, v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    if (d[t] == inf) return false;
    return true;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

inline int pos(int x, int y, int z)
{
    return (x * n + y) * 2 + z;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n >> k;
        s = 0; t = 2;
        add(0, 1, k, 0);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                add(1, pos(i, j, 0), inf, 0),
                add(pos(i, j, 0), pos(i, j, 1), 1, -read()),
                add(pos(i, j, 0), pos(i, j, 1), inf, 0);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                h[i][j] = read();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                if (i == 1 || i == n || j == 1 || j == n)
                    add(pos(i, j, 1), t, inf, 0);
                if (i + 1 <= n && h[i][j] > h[i + 1][j])
                    add(pos(i, j, 1), pos(i + 1, j, 0), inf, 0);
                if (i - 1 >= 1 && h[i][j] > h[i - 1][j])
                    add(pos(i, j, 1), pos(i - 1, j, 0), inf, 0);
                if (j + 1 <= n && h[i][j] > h[i][j + 1])
                    add(pos(i, j, 1), pos(i, j + 1, 0), inf, 0);
                if (j - 1 >= 1 && h[i][j] > h[i][j - 1])
                    add(pos(i, j, 1), pos(i, j - 1, 0), inf, 0);
            }
        cout << -edmonds_karp() << endl;
    }
    return 0;
}

HOJ2739 The Chinese Postman Problem

类似于欧拉回路的建图。先设定所有的边都被走过一次,然后观察哪些结点的出入度不匹配,连到源点和汇点上。无解的情况是图不联通或者有的点无出度或无入度。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
using namespace std;

#define N 105
#define M 5005
#define inf 0x3f3f3f3f

int test, n, m, sum, du[N], v1[N], v2[N], v3[N], x[M], y[M], z[M];
int s, t, head[N], cnt, v[N], d[N], from[N], inc[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0, v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    if (d[t] == inf) return false;
    return true;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

void dfs(int x)
{
    v3[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && !v3[edge[i].to])
            dfs(edge[i].to);
}

void init()
{
    memset(head, 0, sizeof head);
    memset(du, 0, sizeof du);
    memset(v1, 0, sizeof v1);
    memset(v2, 0, sizeof v2);
    memset(v3, 0, sizeof v3);
    cnt = 1; sum = 0;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n >> m;
        s = 0; t = n + 1;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x[i] >> y[i] >> z[i];
            --du[++x[i]]; ++du[++y[i]]; sum += z[i];
            v1[x[i]] = v2[y[i]] = 1;
            add(x[i], y[i], inf, z[i]);
        }
        dfs(1);
        for (int i = 1; i <= n; ++i)
            if (!v1[i] || !v2[i] || !v3[i])
                { puts("-1"); goto end; }
        for (int i = 1; i <= n; ++i)
            if (du[i] > 0) add(s, i, du[i], 0);
            else if (du[i] < 0) add(i, t, -du[i], 0);
        cout << sum + edmonds_karp() << endl;
        end:;
    }
    return 0;
}

POJ3680 Intervals

转化为求 k 次从数轴左端走到数轴右端的模型。把区间看作是只能走一次的隧道,权值为 w,其它部分权值为 0。从左端到右端走 k 次就可以保证区间的最大重叠次数不超过 k。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;

#define N 405
#define M 8005
#define inf 0x3f3f3f3f

int test, n, k, x[N], y[N], z[N];
int s, t, head[N], cnt, v[N], d[N], from[N], inc[N];
vector<int> c;

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0; v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    return d[t] != inf;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
    c.resize(0);
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n >> k;
        s = 0; t = n * 2 + 1;
        for (int i = 1; i <= n; ++i)
        {
            cin >> x[i] >> y[i] >> z[i],
            c.push_back(x[i]), c.push_back(y[i]);
        }
        sort(c.begin(), c.end());
        for (int i = 1; i <= 2 * n + 1; ++i)
            add(i - 1, i, k, 0);
        for (int i = 1; i <= n; ++i)
            add(lower_bound(c.begin(), c.end(), x[i]) - c.begin() + 1,
              lower_bound(c.begin(), c.end(), y[i]) - c.begin() + 1, 1, -z[i]);
        cout << -edmonds_karp() << endl;
    }
    return 0;
}

SPOJBOXES Boxes

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;

#define N 1005
#define M 8005
#define inf 0x3f3f3f3f

int test, n;
int s, t, head[N], cnt, v[N], d[N], from[N], inc[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0; v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    return d[t] != inf;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n;
        s = 0; t = n + 1;
        for (int i = 1; i < n; ++i)
            add(i, i + 1, inf, 1), add(i + 1, i, inf, 1);
        add(n, 1, inf, 1), add(1, n, inf, 1);
        for (int x, i = 1; i <= n; ++i)
        {
            if ((x = read())) add(s, i, x, 0);
            add(i, t, 1, 0);
        }
        cout << edmonds_karp() << endl;
    }
    return 0;
}

JDFZOJ2497 餐巾计划问题

现在看到这样的问题已经不觉得难了。感觉好极了 >o<

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>
using namespace std;

#define N 2000
#define M 30000
#define inf 0x3f3f3f3f

int test, n, p, a, fast, b, slow;
int s, t, head[N], v[N], d[N], from[N], inc[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0; v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    return d[t] != inf;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

inline int pos(int x, int y)
{
    return x * 2 + y;
}

int main()
{
    cin >> n >> p >> a >> fast >> b >> slow;
    s = 0; t = 1;
    for (int x, i = 1; i <= n; ++i)
    {
        x = read();
        add(s, pos(i, 0), inf, p);
        add(pos(i, 0), t, x, 0), add(s, pos(i, 1), x, 0);
    }
    for (int i = 1; i < n; ++i)
        add(pos(i, 0), pos(i + 1, 0), inf, 0),
        add(pos(i, 1), pos(i + 1, 1), inf, 0);
    for (int i = 1; i + a <= n; ++i)
        add(pos(i, 1), pos(i + a, 0), inf, fast);
    for (int i = 1; i + b <= n; ++i)
        add(pos(i, 1), pos(i + b, 0), inf, slow);
    cout << edmonds_karp() << endl;
    return 0;
}

BZOJ2597 [Wc2007]石头剪子布

神奇的补集转化思想,神奇的建图。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

#define N 10005
#define M 200005
#define inf 0x3f3f3f3f

int n, pos[105][105], ans[105][105];
int s, t, head[N], d[N], v[N], inc[N], from[N];

struct graph
{
    int next, to, val, cost;
    graph() {}
    graph(int _next, int _to, int _val, int _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[M];

inline void add(int x, int y, int z, int w)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof v);
    memset(d, 0x3f, sizeof d);
    d[s] = 0; v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    return d[t] != inf;
}

int update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

int edmonds_karp()
{
    int re = 0;
    while (spfa())
        re += update();
    return re;
}

int main()
{
    cin >> n;
    int tot = n;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            pos[i][j] = ++tot;
    s = 0; t = ++tot;
    for (int x, i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            cin >> x;
            if (j <= i) continue;
            add(s, pos[i][j], 1, 0);
            if (x != 0) add(pos[i][j], i, 1, 0);
            if (x != 1) add(pos[i][j], j, 1, 0);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < n; ++j)
            add(i, t, 1, j * j - (j - 1) * (j - 1));
    cout << n * (n - 1) * (n - 2) / 6 +
            (n * (n - 1) / 2 - edmonds_karp()) / 2 << endl;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            for (int k = head[pos[i][j]]; k; k = edge[k].next)
                if (edge[k].to != s && !edge[k].val)
                {
                    if (edge[k].to == i) ans[j][i] = 0, ans[i][j] = 1;
                    else ans[j][i] = 1, ans[i][j] = 0;
                }
    for (int i = 1; i <= n; ++i, puts(""))
        for (int j = 1; j <= n; ++j)
            cout << ans[i][j] << ' ';
    return 0;
}