POJ 3422 Kaka's Matrix Travels （最小费用最大流）

时间：2021-06-11 05:36:03

POJ 3422 Kaka's Matrix Travels


题意：有一个N*N的方格，每一个方格里面有一个数字。如今卡卡要从左上角走到右下角，规定每次仅仅能向下或者向右走。每次走到一个格子，将得到该格子的数字，而且该格子的数字变为0。当卡卡走一次时，非常easy求出最大值，问卡卡走k次，可以得到的最大值为多少。

思路：最小费用最大流
关键是怎样构图
1. 将N*N个格点拆分为两个点（i，i + N*N），每一个点之间连一条流量为1，费用为-w的边。再连一条流量为k，费用为0的边。这样就保证了每一个点之间能够走k次。且最多仅仅有一次能拿到费用。
2. 将每一个点与其以下、右边的点连边。流量为k。费用为0.
3. 构造两个源点、汇点。

源点和左上角连边，流量为k，费用为0. 右下角与汇点连边。流量为k，费用为0.


至此，容量网络已经构成。

每次在残余网络中找费用最短路进行增广就可以。


代码：
/*

ID: wuqi9395@126.com

PROG:

LANG: C++

*/

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<string>

#include<fstream>

#include<cstring>

#include<ctype.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define INF (1 << 20)

#define LINF (1LL << 60)

#define PI acos(-1.0)

#define mem(a, b) memset(a, b, sizeof(a))

#define rep(i, a, n) for (int i = a; i < n; i++)

#define per(i, a, n) for (int i = n - 1; i >= a; i--)

#define eps 1e-6

#define debug puts("===============")

#define pb push_back

#define mkp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

#define SZ(x) ((int)(x).size())

#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)

typedef long long ll;

typedef unsigned long long ULL;

const int maxn = 5555;

const int maxm = 500000;

struct node {

    int v, cap, nxt, cost;

} e[maxm * 2];

int g[maxn], cnt, st, ed, n, m;

int ans, flow;

int nt, k;

void add(int u, int v, int cap, int cost) {

    e[++cnt].v = v;

    e[cnt].cap = cap;

    e[cnt].cost = cost;

    e[cnt].nxt = g[u];

    g[u] = cnt;

    e[++cnt].v = u;

    e[cnt].cap = 0;

    e[cnt].cost = -cost;

    e[cnt].nxt = g[v];

    g[v] = cnt;

}

void init() {

    cnt = 1;

    ans = flow = 0;

    memset(g, 0, sizeof(g));

    // 加边

    int w;

    int p = nt * nt;

    for (int i = 1; i <= nt; i++) {

        for (int j = 1; j <= nt; j++) {

            scanf("%d", &w);

            int id = (i - 1) * nt + j;

            add(id, id + p, 1, -w);

            add(id, id + p, k, 0);

            if (i < nt) add(id + p, id + nt, k, 0);

            if (j < nt) add(id + p, id + 1, k, 0);

        }

    }

    st = 0, ed = p * 2 + 1;

    n = ed;

    add(st, 1, k, 0);

    add(p * 2, ed, k, 0);

}

int dis[maxn], que[maxn], pre[maxn];

bool vis[maxn];

bool spfa() {

    int font = 0, rear = 1;

    for(int i = 0; i <= n; i ++) {

        dis[i] = INF;

        vis[i] = false;

    }

    dis[st] = 0;

    que[0] = st;

    vis[st] = true;

    while(rear != font) {

        int u = que[font++];

        font %= n;

        vis[u] = false;

        for(int i = g[u]; i; i = e[i].nxt) {

            int v = e[i].v;

            if(e[i].cap && dis[v] > dis[u] + e[i].cost) {

                dis[v] = dis[u] + e[i].cost;

                pre[v] = i;

                if(!vis[v]) {

                    vis[v] = true;

                    que[rear++] = v;

                    rear %= n;

                }

            }

        }

    }

    if(dis[ed] == INF) return false;

    return true;

}

void augment() {

    int u, p, mi = INF;

    for(u = ed; u != st; u = e[p ^ 1].v) {

        p = pre[u];

        mi = min(mi, e[p].cap);

    }

    for(u = ed; u != st; u = e[p ^ 1].v) {

        p = pre[u];

        e[p].cap -= mi;

        e[p ^ 1].cap += mi;

        ans += mi * e[p].cost;     //  cost记录的为单位流量费用。必须得乘以流量。

    }

    flow += mi;

}

int MCMF() {

    init();

    while(spfa()) augment();

    return ans;

}

int main () {

    while(~scanf("%d%d", &nt, &k)) {

        printf("%d\n", -MCMF());

    }

    return 0;

}

相关文章