「poj 3422」Kaka's Matrix Travels (最大费用最大流，K-方格取数)

发表于 | 分类于 | | + s

poj 3422
题意：给定 $n^2$的矩阵，含有元素值，每次从最左上角开始出发，每次向右或者向下一格。终点是右下角, 每经过一个格子，获取它的值，并把该格子的值变成$0$.问经过$k$次从左上角到右下角。能得到的数值和最大多少。

把走几次看成容量，数值和看出权值。$(w=w_0,cap=c_0)$表示权值$w_0$, 容量$c_0$
本题如果格子值不会变，那么直接点转边，入点到出点连边$(w=a_{i,j},cap=k)$，然后在网格图中连边$(w=0,cap=k)$，然后求最大费用最大流。

但是这里格子值会变化，所以我们要限制多次走这个点获得多次收益的情况。
我们将入点到出点的边拆边，拆成$(w=a_{i,j}, cap=1), (w=0, cap=k-1)$两条边，然后这样做就可以解决问题了，由于最大费用基于最大流，所以一定能完成不超过$k$次(全部数取完后也可以随便选择路径走，等效)。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int INF = 2147483647ll;

    struct edge {
        int u, v, cap, w, nxt;
    } ed[500000 + 5];

    int n, k, hd[10000 + 5], en, s, t, ans;
    int incf[10000 + 5], dis[10000 + 5], pre[10000 + 5], vis[10000 + 5];

    int getIDbyPos(int x, int y) {return (x - 1) * n + y;}
    void ins_c(int u, int v, int cap, int w) {
        ed[++en] = (edge){u, v, cap, w, hd[u]}, hd[u] = en;
        ed[++en] = (edge){v, u, 0, -w, hd[v]}, hd[v] = en;
    }

    queue<int > q;
    bool spfa() {
        for (int i = 0; i <= n * n * 2; ++i) incf[i] = INF, dis[i] = -INF, pre[i] = -1, vis[i] = 0;
        vis[s] = 1, dis[s] = 0, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (e.cap && dis[u] != -INF && dis[e.v] < dis[u] + e.w) {
                    dis[e.v] = dis[u] + e.w;
                    incf[e.v] = min(incf[u], e.cap);
                    pre[e.v] = i;
                    if (!vis[e.v]) vis[e.v] = 1, q.push(e.v);
                }
            }
        }
        //for (int i = 1; i <= n * n * 2; ++i) printf("%d ", dis[i]); puts("");
        return dis[t] != -INF;
    }
    void update() {
        int now = pre[t];
        while (now != -1) {
            ed[now].cap -= incf[t], ed[now ^ 1].cap += incf[t];
            now = pre[ed[now].u];
        }
        ans += incf[t] * dis[t];
    }

    void clean() {
        ans = 0, en = -1, ms(hd, -1);
    }
    int solve() {

        clean();

        scanf("%d%d", &n, &k);

        for (int i = 1; i <= n; ++i)
        for (int x, j = 1; j <= n; ++j) {
            scanf("%d", &x);
            ins_c(getIDbyPos(i, j), getIDbyPos(i, j) + n * n, 1, x);
            ins_c(getIDbyPos(i, j), getIDbyPos(i, j) + n * n, k - 1, 0);
            if (i < n) ins_c(getIDbyPos(i, j) + n * n, getIDbyPos(i + 1, j), k, 0);
            if (j < n) ins_c(getIDbyPos(i, j) + n * n, getIDbyPos(i, j + 1), k, 0);
        }

        s = 1, t = 2 * n * n;
        while (spfa()) update();

        cout << ans;

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------