首页 题解

# Description

Luogu 传送门

# Solution

  • 最大费用最大流

虽然叫方格取数加强版，但是感觉跟方格取数没半毛钱关系（

我们还是要从当前点向下，向右连边。

  • 观察题意，一个点被走过之后权值变为 0，但是还可以继续走，所以我们可以把一个点拆成入点和出点，然后从入点向出点连两条边。

    • 建一条流量为 1，费用为 ww 的边。

    • 再建一条流量为 k−1k - 1，费用为 0 的边。

    表示第一次走可以获得 ww 的收益，但只能走一次，后面再走到当前点时没有收益。

  • 从当前点向下方和右方连一条流量为 kk，费用为 0 的边，仅表示一种联通关系。

超级源点和超级汇点可建可不建，直接用 (1,1)(1, 1) 的入点当源点，(n,n)(n, n) 的出点当汇点即可。

# Code

#include <bits/stdc++.h>
#define P(i, j, t) ((i - 1) * n + j + t * n * n)
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 5e3 + 10;
const int M = 2e5 + 10;
const int INF = 2e9;
int n, k, ans, s, t;
struct node{
    int v, w, cost, nxt;
}edge[M];
int head[N], tot = 1;
inline void add(int x, int y, int z, int cost){
    edge[++tot] = (node){y, z, cost, head[x]};
    head[x] = tot;
}
inline void Add(int x, int y, int z, int cost){
    add(x, y, z, cost), add(y, x, 0, -cost);
}
int dis[N], f[N], p[N];
bool vis[N];
inline bool spfa(){
    queue <int> q;
    memset(vis, 0, sizeof(vis));
    memset(dis, 128, sizeof(dis));
    q.push(s), vis[s] = 1, dis[s] = 0, f[s] = INF;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = head[x]; i; i = edge[i].nxt){
            if(!edge[i].w) continue;
            int y = edge[i].v;
            if(dis[y] < dis[x] + edge[i].cost){
                dis[y] = dis[x] + edge[i].cost;
                f[y] = min(f[x], edge[i].w), p[y] = i;
                if(!vis[y]) vis[y] = 1, q.push(y);
            }
        }
    }
    return dis[t] > -INF;
}
inline void solve(){
    while(spfa()){
        int x = t;
        while(x != s){
            int i = p[x];
            edge[i].w -= f[t], edge[i ^ 1].w += f[t];
            x = edge[i ^ 1].v;
        }
        ans += dis[t] * f[t];
    }
}
int main(){
    n = read(), k = read();
    s = 1, t = P(n, n, 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j){
            int w = read();
            Add(P(i, j, 0), P(i, j, 1), 1, w);
            Add(P(i, j, 0), P(i, j, 1), k - 1, 0);
            if(i < n) Add(P(i, j, 1), P(i + 1, j, 0), k, 0);
            if(j < n) Add(P(i, j, 1), P(i, j + 1, 0), k, 0);
        }
    solve();
    write(ans), puts("");
    return 0;
}