Skip to content

洛谷 - P2045 方格取数加强版

题解968 字
# 洛谷 # 图论 # 网络流 # 费用流
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

给出一个 n×nn \times n 的矩阵，每一格有一个非负整数 Ai,jA_{i, j} 现在从 (1,1)(1, 1) 出发，可以往右或者往下走，最后到达 (n,n)(n, n)。每到达一格，把该格的数取出并将原位置归 00，这样一共走 kk 次，请你求出走 kk 次所达到的方格的数的和的最大值。

#输入格式

第一行两个数 n,kn, k。

接下来 nn 行，每行 nn 个数，分别表示矩阵上的每个格子中的数。

#输出格式

走 kk 次所达到的方格的数的和的最大值。

#输入输出样例

输入样例 #1

3 1
1 2 3
0 2 1
1 4 2

输出样例 #1

11

#数据范围与约定

对于 100%100\% 的数据，1≤n≤501 \leq n \leq 50，0≤k≤100 \leq k \leq 10，0≤Ai,j≤10000 \leq A_{i, j} \leq 1000。

#思路

按照网格建立网络，将每个点拆成入点和出点两个点，入点向出点连两条边：一条 flow=1,cost=−val\mathit{flow} = 1, \mathit{cost} = -\mathit{val} 表示第一次经过（负数是为了把最大费用最大流转化为最小费用最大流），另一条 flow=inf⁡,cost=0\mathit{flow} = \inf, \mathit{cost} = 0 供后几次经过使用。每个点的出点向右方和下方连 flow=inf⁡,cost=0\mathit{flow} = \inf, \mathit{cost} = 0 的边。之后将从超级源点向 (1,1)(1, 1)、从 (n,n)(n, n) 向超级汇点分别连两条 flow=k,cost=0\mathit{flow} = k, \mathit{cost} = 0 的边，再求出最小费用最大流即可。

最后输出答案时别忘了将负数再转回正数。

#代码

C++
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
#include <cstring>
#include <iostream>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 5005,
          M = 100005,
          INF = 0x3f3f3f3f;

int n, k, s, t, ans;

// Graph
int idx, head[N], ver[M << 1], next[M << 1];
std::pair<int, int> edge[M << 1];
//      <flow, cost>

void add(int u, int v, int flow, int cost) {
    next[idx] = head[u];
    ver[idx] = v;
    edge[idx] = std::make_pair(flow, cost);
    head[u] = idx++;
}

inline int id(int i, int j, int k = 0) {
    return (i - 1) * n + j + k * n * n;
}

// Dinic
int dist[N];
bool vis[N];

bool spfa() {
    memset(vis, 0x00, sizeof(vis));
    memset(dist, 0x3f, sizeof(dist));

    std::queue<int> q;
    q.push(s);
    dist[s] = 0;
    vis[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;

        for (int i = head[u]; ~i; i = next[i]) {
            int v = ver[i],
                c = edge[i].first,
                w = edge[i].second;

            if (c > 0 && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }

    return dist[t] != INF;
}

int dinic(int u, int limit) {
    if (u == t) return limit;

    int flow = 0;
    vis[u] = true;
    for (int i = head[u]; ~i && flow < limit; i = next[i]) {
        int v = ver[i],
            c = edge[i].first,
            w = edge[i].second;
        if (dist[v] == dist[u] + w && c && !vis[v]) {
            int k = dinic(v, std::min(c, limit - flow));
            if (!k) dist[v] = INF;
            edge[i].first -= k;
            edge[i ^ 1].first += k;
            flow += k;
            ans += k * w;
        }
    }
    vis[u] = false;

    return flow;
}

int main() {
    std::ios::sync_with_stdio(false);

    memset(head, 0xff, sizeof(head));

    cin >> n >> k;

    s = 0;
    add(s, id(1, 1), k, 0);
    add(id(1, 1), s, 0, 0);

    t = id(n, n, 1) + 1;
    add(id(n, n, 1), t, k, 0);
    add(t, id(n, n, 1), 0, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int w;
            cin >> w;

            add(id(i, j), id(i, j, 1), 1, -w);
            add(id(i, j, 1), id(i, j), 0, w);

            add(id(i, j), id(i, j, 1), INF, 0);
            add(id(i, j, 1), id(i, j), 0, 0);

            if (i < n) {
                add(id(i, j, 1), id(i + 1, j), INF, 0);
                add(id(i + 1, j), id(i, j, 1), 0, 0);
            }

            if (j < n) {
                add(id(i, j, 1), id(i, j + 1), INF, 0);
                add(id(i, j + 1), id(i, j, 1), 0, 0);
            }
        }
    }

    while (spfa()) dinic(s, INF);

    cout << -ans << endl;
    return 0;
}