POJ3422或洛谷2045 Kaka's Matrix Travels

POJ原题链接

洛谷原题链接

很裸的费用流。
将每个点\(x\)拆成\(x_1,x_2\)，并从\(x_1\)向\(x_2\)连一条容量为\(1\)，费用为该点的权值的边，以及一条容量为\(+\infty\)，费用为\(0\)的边。
设\(x\)下方的点为\(y\)，右边的点为\(z\)（如果存在），则从\(x_2\)向\(y_1,z_1\)连一条容量为\(+\infty\)，费用为\(0\)的边。
最后由源点向原坐标为\((1,1)\)的点连一条容量为\(k\)，费用为\(0\)的边，由原坐标为\((n,n)\)的点向汇点连一条容量为\(k\)，费用为\(0\)的边。
然后跑最大费用最大流即可。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e4 + 10;
const int M = 1e5 + 10;
int fi[N], di[M], da[M], ne[M], co[M], la[M], cn[M], q[M << 2], dis[N], l = 1, st, ed, n;
bool v[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void add(int x, int y, int z, int c)
{
    di[++l] = y;
    da[l] = z;
    co[l] = c;
    ne[l] = fi[x];
    fi[x] = l;
    di[++l] = x;
    da[l] = 0;
    co[l] = -c;
    ne[l] = fi[y];
    fi[y] = l;
}
inline int minn(int x, int y)
{
    return x < y ? x : y;
}
inline int ch(int x, int y)
{
    return (x - 1) * n + y;
}
bool spfa()
{
    int head = 0, tail = 1, i, x, y;
    memset(dis, 250, sizeof(dis));
    dis[st] = 0;
    q[1] = st;
    while (head ^ tail)
    {
        x = q[++head];
        v[x] = 0;
        for (i = fi[x]; i; i = ne[i])
            if (dis[y = di[i]] < dis[x] + co[i] && da[i] > 0)
            {
                dis[y] = dis[x] + co[i];
                la[y] = x;
                cn[y] = i;
                if (!v[y])
                {
                    v[y] = 1;
                    q[++tail] = y;
                }
            }
    }
    return dis[ed] > -1e7;
}
int main()
{
    int i, j, m, x, y, mi, s = 0, o;
    n = re();
    m = re();
    st = (o = n * n) << 1 | 1;
    ed = st + 1;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            x = re();
            y = ch(i, j);
            add(y, y + o, 1, x);
            add(y, y + o, 1e9, 0);
            if (i < n)
                add(y + o, ch(i + 1, j), 1e9, 0);
            if (j < n)
                add(y + o, ch(i, j + 1), 1e9, 0);
        }
    add(st, 1, m, 0);
    add(st ^ 1, ed, m, 0);
    while (spfa())
    {
        mi = 1e9;
        for (i = ed; i ^ st; i = la[i])
            mi = minn(mi, da[cn[i]]);
        s += mi * dis[ed];
        for (i = ed; i ^ st; i = la[i])
        {
            da[cn[i]] -= mi;
            da[cn[i] ^ 1] += mi;
        }
    }
    printf("%d", s);
    return 0;
}

POJ3422或洛谷2045 Kaka's Matrix Travels

原文：https://www.cnblogs.com/Iowa-Battleship/p/9671121.html