POJ3422 Kaka's Matrix Travels

网络流

Vjudge

费用流模板题。

将每个点拆成一个入点和一个出点，在入点与出点间连一条容量为 $1$ ，费用为点权的边，再连一条容量为 $k-1$ ，费用为 $0$ 的边。然后再在相邻的点之间连边就行了。然后直接跑最大费用最大流。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
const int INF = 0x3f3f3f3f;
const int MIINF = 0xcfcfcfcf;
const int MAXN = 100;
const int MAXM = 8 * MAXN * MAXN - 4 * MAXN;
int n, k, edge = -1, maxCost, sp, ep;
int firstEdge[MAXN * MAXN | 1], lst[MAXN * MAXN | 1], dist[MAXN * MAXN | 1], minFlow[MAXN * MAXN << 1], g[MAXN | 1][MAXN | 1];
struct Edge {
    int to, f, w, nxt;
    Edge(){}
    Edge(int a, int b, int c, int d) {
        to = b;
        f = c;
        w = d;
        nxt = firstEdge[a];
    }
} e[MAXM + 2];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int a, int b, int c, int d) {
    e[++edge] = Edge(a, b, c, d);
    firstEdge[a] = edge;
}
bool Augment() {
    std::queue <int> q;
    bool vis[MAXN * MAXN << 1];
    while(!q.empty()) q.pop();
    memset(vis, false, sizeof(vis));
    memset(dist, MIINF, sizeof(dist));
    dist[sp] = 0;
    minFlow[sp] = INF;
    q.push(sp);
    do {
        int from = q.front();
        q.pop();
        vis[from] = false;
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, f = e[k].f, w = e[k].w;
            if(f > 0 && dist[to] < dist[from] + w) {
                dist[to] = dist[from] + w;
                minFlow[to] = std::min(minFlow[from], f);
                lst[to] = k;
                if(!vis[to]) {
                    q.push(to);
                    vis[to] = true;
                }
            }
        }
    } while(!q.empty());
    return dist[ep] != MIINF;
}
int EK(int flow) {
    while(flow > 0 && Augment()) {
        maxCost += minFlow[ep] * dist[ep];
        int tmp = ep;
        while(tmp != sp) {
            e[lst[tmp]].f -= minFlow[ep];
            e[lst[tmp] ^ 1].f += minFlow[ep];
            tmp = e[lst[tmp] ^ 1].to;
        }
    }
}
inline int ID(int x, int y, int z) {
    return (x - 1) * n + y + z * n * n;
}
int main() {
    n = read();
    k = read(); 
    sp = 1;
    ep = n * n << 1;
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            int val = read();
            addEdge(ID(i,j, 0), ID(i, j, 1), 1, val);
            addEdge(ID(i, j, 1), ID(i, j, 0), 0, -val);
            addEdge(ID(i, j, 0), ID(i, j, 1), k - 1, 0);
            addEdge(ID(i, j, 1), ID(i, j, 0), 0, 0);
            if(j < n) {
                addEdge(ID(i, j, 1), ID(i, j + 1, 0), k, 0);
                addEdge(ID(i, j + 1, 0), ID(i, j, 1), 0, 0);
            }
            if(i < n) {
                addEdge(ID(i, j, 1), ID(i + 1, j, 0), k, 0);
                addEdge(ID(i + 1, j, 0), ID(i, j, 1), 0, 0);
            }
        }
    }
    EK(k);
    printf("%d\n", maxCost);
    return 0;
}