-网络流-费用流- [洛谷 P2045]方格取数加强版

题目描述

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入格式

第一行两个数n,k（1<=n<=50, 0<=k<=10）

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式

一个数,为最大和

输入样例

3 1
1 2 3
0 2 1
1 4 2

输出样例

11

说明

每个格子中的数不超过1000

Solution

这个题目要求走k次，每走一次将经过方格中的数取出，取过的数不能再取

显然DP做不了，如果能做请私聊我

那么，我们就要拿出终极武器——网络流中的费用流。

那么该如何建模呢？

先拆点，将每个点拆成两个点

因为题目要求从(1,1)开始，从(n,n)结束，那么就可以将源点连向(1,1)，将(n,n)连向汇点。

因为只能向下走和向右走，所以就将每个点向右和向下连边。

对于有数的点建一条边流量为1，费用为这个数。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 100010
#define INF 2000000000
struct Edge {
    int v, nx, fl, w;
}e[MAXN];
int n, m, r, k, head[MAXN], dis[MAXN], ecnt = 1, flow[MAXN], maxf, minc, la[MAXN], pre[MAXN], x, y, z, f, mp[60][60];
bool vis[MAXN];
std::queue <int> q;
int min(int a, int b) {
    if (a < b) return a;
    else return b;
}
void add(int f, int t, int fl, int w) {
    e[++ecnt] = (Edge) {t, head[f], fl, w};
    head[f] = ecnt;
    e[++ecnt] = (Edge) {f, head[t], 0, -w};
    head[t] = ecnt;
}
bool spfa(int s, int t) {
    memset(dis, 0x7f, sizeof(dis));
    memset(flow, 0x7f, sizeof(flow));
    memset(vis, 0, sizeof(vis));
    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    pre[t] = -1;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = 0;
        for (int i = head[v]; i; i = e[i].nx) {
            int f = e[i].fl;
            int to = e[i].v;
            if (f > 0 && dis[to] > dis[v] + e[i].w) {
                dis[to] = dis[v] + e[i].w;
                pre[to] = v;
                la[to] = i;
                flow[to] = min(flow[v], f);
                if (!vis[to]) {
                    vis[to] = 1;
                    q.push(to);
                }
            }
        }
    }
    return pre[t] != -1;
}
int g(int i, int j) {
    return (i - 1) * n + j;
}
void mcmf(int s, int t) {
    while (spfa(s, t)) {
        int v = t;
        maxf += flow[t];
        minc += flow[t] * dis[t];
        while (v != s) {
            int k = la[v];
            e[k].fl -= flow[t];
            e[k ^ 1].fl += flow[t];
            v = pre[v];
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    r = 2 * n * n + 1;
    k = 2 * n * n + 2;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &mp[i][j]);
        }
    }
    add(r, g(1, 1), m, 0);
    add(g(n, n) + n * n, k, m, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            add(g(i, j), g(i, j) + n * n, 1, -mp[i][j]);
            add(g(i, j), g(i, j) + n * n, INF, 0);
            if (i < n) {
                add(g(i, j) + n * n, g(i + 1, j), INF, 0);
            }
            if (j < n) {
                add(g(i, j) + n * n, g(i, j + 1), INF, 0);
            }
        }
    }
    mcmf(r, k);
    printf("%d\n", -minc);
    return 0;
}