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

2015.11.27 12:52 Fri| 4 visits oi_2016| ChaosSlover补档计划| Text

BZOJ3218 a + b Problem

神奇的建图姿势:对于点 i,从 s 到 i 连一条权值为 b[i] 的边,从 i 到 s 连一条权值为 w[i] 的边。拆出点 i',从 i 到 i' 连一条权值为 p[i] 的边,从 i' 到能使 i 变奇怪的点 j 连一条权值为 inf 的边。这样 ∑b+∑w-maxflow 就是答案了。

然而按照这样建图的话,边数太大了。我们使用可持久化线段树,让 i' 连向线段 (l[i],r[i]),再让线段树中的结点连向相应的位置。

  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
123
124
125
126
127
128
129
130
#include <bits/stdc++.h>
using namespace std;

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

int n, tot, a[N], b[N], w[N], l[N], r[N], p[N];
int s, t, ans, head[M], d[M];
vector<int> v;

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 node
{
    node *son[2]; int tag;
} *root[N];

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

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

void insert(node *pre, node *&pos, int l, int r, int x, int y)
{
    pos = new node();
    *pos = *pre; pos->tag = tot++;
    add(pos->tag, pre->tag, inf);
    add(pos->tag, y, inf);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) insert(pre->son[0], pos->son[0], l, mid, x, y);
    else insert(pre->son[1], pos->son[1], mid + 1, r, x, y);
}

void query(node *pos, int l, int r, int x, int y, int z)
{
    if (x <= l && r <= y) { add(z, pos->tag, inf); return; }
    int mid = (l + r) >> 1;
    if (x <= mid) query(pos->son[0], l, mid, x, y, z);
    if (y > mid) query(pos->son[1], mid + 1, r, x, y, z);
}

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

int main()
{
    cin >> n;
    s = 0; t = n * 2 + 1; tot = t + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = read(), w[i] = read(), ans += b[i] + w[i],
        l[i] = read(), r[i] = read(), p[i] = read(), v.push_back(a[i]);
    sort(v.begin(), v.end());
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1,
        l[i] = lower_bound(v.begin(), v.end(), l[i]) - v.begin() + 1,
        r[i] = upper_bound(v.begin(), v.end(), r[i]) - v.begin();
    for (int i = 1; i <= n; ++i)
        add(s, i, b[i]), add(i, t, w[i]), add(i, n + i, p[i]);
    root[0] = new node(); root[0]->tag = -1;
    root[0]->son[0] = root[0]->son[1] = root[0];
    for (int i = 1; i <= n; ++i)
        insert(root[i - 1], root[i], 1, n, a[i], i);
    for (int i = 1; i <= n; ++i)
        if (l[i] <= r[i])
            query(root[i - 1], 1, n, l[i], r[i], n + i);
    cout << ans - dinic() << endl;
    return 0;
}

BZOJ1070 [SCOI2007]修车

将每一个修理员拆成 N 个点(好残暴),其中第 i 个点表示他倒数第 i 个修的车,第 i 辆车连向第 j 个修理员拆出的第 k 个点的花费是 t[j][i]*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
 99
100
#include <bits/stdc++.h>
using namespace std;

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

int n, m, c, p;
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)
{
    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);
            }
    }
    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;
}


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

int main()
{
    cin >> m >> n;
    s = 0; t = pos(m, n + 1);
    for (int i = 1; i <= n; ++i)
        add(s, i, 1, 0);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            add(pos(i, j), t, 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int x = read(), k = 1; k <= n; ++k)
                add(i, pos(j, k), 1, x * k);
    cout << fixed << setprecision(2) << 1.0 * edmonds_karp() / n << endl;
    return 0;
}

BZOJ2561 最小生成树

如果使新加入的边 (u,v) 成为最小生成树上的边,那么边权比新加入的边更小的边一定不能够使 u 和 v 连通。从 u 到 v 跑一遍最小割就可以了。数组开小的眼泪……

  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
#include <bits/stdc++.h>
using namespace std;

#define N 20005
#define M 800005
#define inf 0x3f3f3f3f

int n, m, x[M], y[M], w[M], u, v, l;
int s, t, head[N], cnt, d[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;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

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

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

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

int main()
{
    cin >> n >> m;
    if (m < n) { puts("0"); return 0; }
    for (int i = 1; i <= m; ++i)
        x[i] = read(), y[i] = read(), w[i] = read();
    u = read(); v = read(); l = read();
    s = u; t = v;
    init();
    for (int i = 1; i <= m; ++i)
        if (w[i] < l)
            add(x[i], y[i], 1), add(y[i], x[i], 1);
    int ans = dinic();
    init();
    for (int i = 1; i <= m; ++i)
        if (w[i] > l)
            add(x[i], y[i], 1), add(y[i], x[i], 1);
    cout << ans + dinic() << endl;
    return 0;
}

BZOJ2229 [Zjoi2011]最小割

神奇的叫做最小割树的东西。随便选两个点割一下,拿新的最小割更新解,并递归到两个割集中。

  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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;

#define N 155
#define M 50000
#define inf 0x3f3f3f3f

int test, n, m, ans[N][N], pos[N], pos2[N];
bool col[N];
int head[N], cnt, d[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;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

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

queue<int> q;

bool bfs(int s, int t)
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f, int t)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val), t);
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic(int s, int t)
{
    int re = 0;
    while (bfs(s, t))
        re += dfs(s, inf, t);
    return re;
}

void dfs2(int x)
{
    col[x] = true;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && !col[edge[i].to])
            dfs2(edge[i].to);
}

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

void reset()
{
    for (int i = 2; i < cnt; i += 2)
        edge[i].val = edge[i ^ 1].val = (edge[i].val + edge[i ^ 1].val) / 2;
}

void getans(int l, int r)
{
    if (l == r) return;
    reset();
    int cut = dinic(pos[l], pos[r]);
    memset(col, 0, sizeof col);
    dfs2(pos[l]);
    int tl = l - 1, tr = r + 1;
    for (int i = l; i <= r; ++i)
        if (col[pos[i]]) pos2[++tl] = pos[i];
        else pos2[--tr] = pos[i];
    for (int i = l; i <= r; ++i)
        pos[i] = pos2[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; col[i] && j <= n; ++j)
            if (!col[j]) ans[i][j] = ans[j][i] = min(ans[i][j], cut);
    getans(l, tl); getans(tr, r);
}

int main()
{
    cin >> test;
    while (test--)
    {
        memset(ans, 0x7f, sizeof ans);
        cin >> n >> m;
        init();
        for (int x, y, z, i = 1; i <= m; ++i)
            x = read(), y = read(), z = read(),
            add(x, y, z), add(y, x, z);
        for (int i = 1; i <= n; ++i)
            pos[i] = i;
        getans(1, n);
        int q = read();
        while (q--)
        {
            int x = read(), y = 0;
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    if (ans[i][j] <= x) ++y;
            printf("%d\n", y / 2);
        }
        puts("");
    }
    return 0;
}

BZOJ2756 [SCOI2012]奇怪的游戏

如果 N*M 是奇数,那么可以直接算出来最终值的大小,网络流验证一次即可;否则黑白染色后使用二分确定格子最后得到的值。现在已经可以很快想出这种题的解法了好评!

模拟赛 - 省选预热四

原题大模拟赛,考了下面三道题,考傻了我……

jkxing 10 分,szy 70 分,wfy 85分,llx 105 分,都是什么鬼……

BZOJ3144 [Hnoi2013]切糕

建图方式很神奇:把某一个纵坐标的点从上到下串起来,边权为下面的点的和谐度。然后最上面有源点,最下面有汇点,如果不考虑 D 的限制,那么求一次最小割即可。

考虑 D 的限制,从某个坐标高度为 i 的点到相邻坐标高度为点 i-D 的点连一条权值为 inf 的边,表示如果被割掉的是这个点上面的边,那么相邻坐标的高度在 i-D 之内的点上的边就都不能割了。

时至今日仍然感觉网络流的时间复杂度是个谜。

  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 100000
#define M 400000
#define inf 0x3f3f3f3f

int p, q, r, dd, pos[42][42][42];
int s, t, head[N], d[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;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

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

queue<int> que;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!que.empty()) que.pop();
    d[s] = 1; que.push(s);
    while (!que.empty())
    {
        int x = que.front(); que.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                que.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

int main()
{
    cin >> p >> q >> r >> dd;
    s = 0; t = 1;
    memset(pos, -1, sizeof pos);
    for (int tot = 1, i = 1; i <= r; ++i)
        for (int j = 1; j <= p; ++j)
            for (int k = 1; k <= q; ++k)
            {
                pos[i][j][k] = ++tot;
                if (i == 1) add(s, tot, read());
                else add(pos[i - 1][j][k], tot, read());
                if (i == r) add(tot, t, inf);
                if (i > dd)
                    add(tot, pos[i - dd][j - 1][k], inf),
                    add(tot, pos[i - dd][j][k - 1], inf),
                    add(tot, pos[i - dd][j + 1][k], inf),
                    add(tot, pos[i - dd][j][k + 1], inf);
            }
    cout << dinic() << endl;
    return 0;
}

BZOJ3876 [Ahoi2014]支线剧情

每一条边拆成一条容量为 1 权值为负无穷的边和一条容量为正无穷权值为 t 的边,每一个点向汇点连一条权值为 0 容量为正无穷的边。然后跑费用流直到增广路的权值为 0。把费用流得到的答案加起来再加上 ∑k 个正无穷(正无穷+正无穷=2*正无穷)就好了。

然而 BZOJ AC 了,然而考试的时候只得到了 70 分。听说有更神的建图方式(有下界的最小流?)。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 350
#define M 100000
#define inf 0x3f3f3f3f

int n, sum, ans;
int s, t, head[N], v[N], d[N], inc[N], from[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(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 main()
{
    cin >> n;
    s = 1; t = n + 1;
    for (int x, y, k, i = 1; i <= n; ++i)
    {
        cin >> k; sum += k;
        for (int j = 1; j <= k; ++j)
        {
            x = read(), y = read();
            add(i, x, 1, y - 200000); add(i, x, inf, y);
        }
        add(i, t, inf, 0);
    }
    do { spfa(); ans += update(); } while (d[t]);
    cout << ans + 200000 * sum << endl;
    return 0;
}

那个能快好几十倍的代码:

先把下界的限制统计进答案。然后跑一遍弗洛伊德。设源点的入度是正无穷。如果某一个点的入度大于出度或者出度大于入度,就从超级源点或者向超级汇点连边权为 0 的边(就像其他的题一样),将所有的点分成两个集合(其实还有根本没连边的点,但不需要考虑了)。然后在两个集合之间连边,边权为两个点之间的最短路长度,容量为 inf。最后跑一遍裸费用流,加上最开始统计的答案。这样建出来的图是一个二分图。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 350
#define M 100000
#define inf 0x3f3f3f3f

int n, ans, in[N], out[N], dist[N][N];
int s, t, head[N], v[N], d[N], inc[N], from[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(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()
{
    memset(dist, 0x3f, sizeof dist);
    cin >> n;
    s = 1; t = n + 1;
    for (int x, y, k, i = 1; i <= n; ++i)
    {
        cin >> k; out[i] += k;
        for (int j = 1; j <= k; ++j)
            x = read(), y = read(),
            dist[i][x] = y, ++in[x], ans += y;
        dist[i][i] = 0;
    }
    in[1] = inf;
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    for (int i = 1; i <= n; ++i)
        if (in[i] > out[i])
            add(s, i, in[i] - out[i], 0);
        else if (in[i] < out[i])
            add(i, t, out[i] - in[i], 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (in[i] > out[i] && in[j] < out[j] && dist[i][j] != inf)
                add(i, j, inf, dist[i][j]);
    cout << ans + edmonds_karp() << endl;
    return 0;
}

BZOJ3774 最优选择

考虑一维的情况,建图如图所示(二维也是一样的,只不过画起来比较难看)。图中粗边表示边权为正无穷(永远不会被割掉)。每一对点分别和源点和汇点连起来,容量为 b。可以发现这一对边中一定会有一条被割掉。很显然看到格子,就会想到黑白染色啊。设 i 被染成黑色,源点向 i' 连一条边权为 ai 的边(抱歉图里面把这条边画反了),否则 i 向汇点连一条边权为 ai 的边,如果割掉这一条边代表我们真的选择了 a。

将初始权值设为 2*∑b。考虑我们如果不选择 i,那么在图中就保留了 ai 的边,从而就可以确定有一条权值为 bi 的边会被割掉了。再观察一下这张图,如果存在 i 周围的点 x,ax 没有被割掉,那么另一条权值为 bi 的边又会被割掉。当然,如果我们同时割掉了 ai 和所有的 ax,还是一定会有一条 bi 被割掉。因此像这样建图大概是满足正确性的……(这建图方式真是太神了)

  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
#include <bits/stdc++.h>
using namespace std;

#define N 5500
#define M 100000
#define inf 0x3f3f3f3f

int n, m, ans;
int s, t, head[N], d[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;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

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

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

inline int pos(int x, int y, int z)
{
    if (x < 1 || x > n || y < 1 || y > m)
        return -1;
    return ((x - 1) * m + y) * 2 + z;
}

int main()
{
    cin >> n >> m;
    s = 0; t = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if ((i + j) % 2)
                add(s, pos(i, j, 1), read());
            else
                add(pos(i, j, 0), t, read());
    for (int x, i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            x = read(), ans += x * 2;
            add(s, pos(i, j, 0), x);
            add(pos(i, j, 0), pos(i, j, 1), inf);
            add(pos(i, j, 1), t, x);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if ((i + j) % 2)
            {
                add(pos(i, j, 0), pos(i - 1, j, 0), inf);
                add(pos(i, j, 0), pos(i + 1, j, 0), inf);
                add(pos(i, j, 0), pos(i, j - 1, 0), inf);
                add(pos(i, j, 0), pos(i, j + 1, 0), inf);
                add(pos(i, j, 1), pos(i - 1, j, 1), inf);
                add(pos(i, j, 1), pos(i + 1, j, 1), inf);
                add(pos(i, j, 1), pos(i, j - 1, 1), inf);
                add(pos(i, j, 1), pos(i, j + 1, 1), inf);
            }
    cout << ans - dinic() << endl;
    return 0;
}

BZOJ2756 [SCOI2012]奇怪的游戏

建图很简单啊。黄学长少判了几个 -1,可以被卡掉。

然而我这题 WA 了整整一小时(眼泪),原因是加容量为 inf 的弧的时候不能加反向弧!否则限制就会顺着反向弧流走!流走了啊……

加反向弧的反例:

1
1 4
1 2 6 5
  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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;

#define N 2000
#define M 20000
#define inf (1ll << 50)

int test, n, m, a[45][45];
int s, t, head[N], cnt, d[N];

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

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

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

long long dfs(int x, long long f)
{
    if (x == t) return f;
    long long temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            long long k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

long long dinic()
{
    long long re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}


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

inline int pos(int x, int y)
{
    return (x - 1) * m + y;
}

bool check(long long x)
{
    init();
    s = 0; t = n * m + 1;
    long long tot = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if ((i + j) & 1)
                add(s, pos(i, j), x - a[i][j]), tot += x - a[i][j];
            else
                add(pos(i, j), t, x - a[i][j]);
            if ((i + j) & 1)
            {
                if (i != 1) add(pos(i, j), pos(i - 1, j), inf);
                if (i != n) add(pos(i, j), pos(i + 1, j), inf);
                if (j != 1) add(pos(i, j), pos(i, j - 1), inf);
                if (j != m) add(pos(i, j), pos(i, j + 1), inf);
            }
        }
    if (dinic() != tot) return false;
    return true;
}

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;
}

int main()
{
    cin >> test;
    while (test--)
    {
        cin >> n >> m;
        int maxn = 0;
        long long sum[2] = {0};
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
            {
                a[i][j] = read();
                sum[(i + j) & 1] += a[i][j];
                maxn = max(maxn, a[i][j]);
            }
        if ((n * m) & 1)
        {
            long long ans = sum[0] - sum[1];
            if (ans >= maxn && check(ans))
                cout << (n * m * ans - sum[0] - sum[1]) / 2 << endl;
            else puts("-1");
        }
        else
        {
            if (sum[0] != sum[1])
                { puts("-1"); continue; }
            long long l = maxn, r = inf, ans = 0;
            while (l <= r)
            {
                long long mid = (l + r) >> 1;
                if (check(mid))
                    r = mid - 1, ans = mid;
                else l = mid + 1;
            }
            if (ans == 0) puts("-1");
            else cout << (n * m * ans - sum[0] - sum[1]) / 2 << endl;
        }
    }
    return 0;
}

模拟赛 - 省选预热四

又考了一次网络流……这次真是……

第一题就是需要求边不相交的最短路数量,直接 SPFA 建图玩 Dinic 啦!

BZOJ3158&3275 千钧一发

模拟赛第二题,老师手打的题面(老师辛苦了),于是把【不存在】的“不”吃掉了!吃掉了啊……

于是题目就变成了求一般图最大团,NP 完全……考场上我脑抽写了一个一般图最小点权覆盖(当然,这并不对),单纯形解线性规划…….

至于 BZOJ3275,这两道题实际上是一样的。

好吧。这是修改过的单纯形代码,能过原题 50% 的数据

  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
#include <bits/stdc++.h>
using namespace std;

#define N 20005
#define M 1005
#define eps 1e-7
#define inf 1e10

int n, a[M], tot;

struct lin_pro
{
    int n, m;
    double a[M][N], b[M], c[N], v;

    void pivot(int l, int e)
    {
        b[l] /= a[l][e];
        for (int i = 1; i <= n; ++i)
            if (i != e)
                a[l][i] /= a[l][e];
        a[l][e] = 1 / a[l][e];
        for (int i = 1; i <= m; ++i)
            if (i != l && fabs(a[i][e]) > eps)
            {
                b[i] -= a[i][e] * b[l];
                for (int j = 1; j <= n; ++j)
                    if (j != e)
                        a[i][j] -= a[i][e] * a[l][j];
                a[i][e] = -a[i][e] * a[l][e];
            }
        v += c[e] * b[l];
        for (int i = 1; i <= n; ++i)
            if (i != e)
                c[i] -= c[e] * a[l][i];
        c[e] = -c[e] * a[l][e];
    }

    double simplex()
    {
        while (true)
        {
            int e = 0;
            for (int i = 1; i <= n; ++i)
                if (c[i] > eps)
                    { e = i; break; }
            if (!e) return v;
            double temp = inf; int l = 0;
            for (int i = 1; i <= m; ++i)
                if (a[i][e] > eps && b[i] / a[i][e] < temp)
                    temp = b[i] / a[i][e], l = i;
            if (temp == inf) return inf;
            pivot(l, e);
        }
    }
} lp;

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

set<long long> s;

inline bool check(int x, int y)
{
    if (gcd(x, y) != 1) return false;
    if (s.find(1ll * x * x + 1ll * y * y) == s.end()) return false;
    return true;
}

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;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= 150000; ++i)
        s.insert(1ll * i * i);
    if (n > 200)
    {
        for (int x, i = 1; i <= n; ++i)
        {
            x = read();
            if (a[i] % 2 == 0) tot += x;
        }
        cout << tot << endl;
        return 0;
    }
    lp.m = n;
    for (int i = 1; i <= n; ++i)
        lp.b[i] = read(), tot += lp.b[i];
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            if (check(a[i], a[j]))
                lp.c[++lp.n] = 1, lp.a[i][lp.n] = 1, lp.a[j][lp.n] = 1;
    cout << fixed << setprecision(0) << tot - lp.simplex() << endl;
    return 0;
}

正解是二分图最大独立集。将石头按奇偶性分成两组,然后在反图中这就是一个二分图。

正经的代码:

  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
#include <bits/stdc++.h>
using namespace std;

#define N 1005
#define M 1000005
#define inf 0x3f3f3f3f
#define sqr(x) ((x) * (x))

int n, a[N], tot, s, t, head[N], d[N];

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

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

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

inline bool issqr(long long x)
{
    return sqr((long long)sqrt(x)) == x;
}

inline bool check(int x, int y)
{
    if (__gcd(x, y) != 1 || !issqr(1ll * x * x + 1ll * y * y))
        return false;
    return true;
}

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;
}

int main()
{
    cin >> n;
    s = 0; t = n + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int x, i = 1; i <= n; ++i)
    {
        tot += (x = read());
        if (a[i] & 1) add(s, i, x);
        else add(i, t, x);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if ((a[i] & 1) && !(a[j] & 1) && check(a[i], a[j]))
                add(i, j, inf);
    cout << tot - dinic() << endl;
    return 0;
}

BZOJ2039 [2009国家集训队]employ人员雇佣

考虑 i 对 j 有 E(i,j) 的了解度,那么在最小割中,相当于如果他们没有都被选或都不被选,会产生 E(i,j) 的代价,如果没有选 i,会产生 E(i,j) 的代价。

那么将每一个人作为点,原点连容量为 Ai 的边,汇点连容量为 ∑Ei 的边,人们两两之间连 2*E(i,j) 的边。

  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 1005
#define M 3000005

int n, s, t, head[N], cnt = 1, d[N];
unsigned int tot;

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

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

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

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

unsigned int dfs(int x, unsigned int f)
{
    if (x == t) return f;
    unsigned int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            unsigned int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

unsigned int dinic()
{
    unsigned int re = 0;
    while (bfs())
        re += dfs(s, 0xffffffffu);
    return re;
}

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;
}

int main()
{
    cin >> n;
    s = 0; t = n + 1;
    for (int i = 1; i <= n; ++i)
        add(s, i, read());
    for (int i = 1; i <= n; ++i)
    {
        int s = 0;
        for (int x, j = 1; j <= n; ++j)
        {
            x = read(); s += x; tot += x;
            if (i < j) add2(i, j, x * 2);
        }
        add(i, t, s);
    }
    cout << tot - dinic() << endl;
    return 0;
}