挺简单一个题，最小割模板

我的感觉就是可能建图的时候会比较麻烦吧，毕竟三个方向。

#include <cctype>

#include <climits>

#include <cstdio>

#include <cstring>

#include <iostream>

#define debug(x) std::cout << #x << " = " << x << std::endl;

#define __OPTIMIZED__INPUT__

int nextInt()

{

    int num = 0;

    char c;

    bool flag = false;

    while ((c = std::getchar()) == ' ' || c == '\r' || c == '\n' || c == '\t');

    if (c == '-')

        flag = true;

    else

        num = c - 48;

    while (std::isdigit(c = std::getchar()))

        num = num * 10 + c - 48;

    return (flag ? - 1 : 1) * num;

}

struct

{

    int to;

    int nex;

    int v;

} e[600001];

int head[600001];

int h[600001], q[600001];

int ans, n, m;

void Insert(const int u, const int v, const int w)

{

    static int tot = 0;

    tot++;

    e[tot].to = v;

    e[tot].v = w;

    e[tot].nex = head[u];

    head[u] = tot;

}

bool bfs()

{

    int now, i;

    std::memset(h, 0xff, sizeof h);

    int t = 0;

    int w = 1;

    q[t] = 1;

    h[1] = 0;

    while (t < w)

    {

        now = q[t];

        t++;

        i = head[now];

        for (int i = head[now]; i; i = e[i].nex)

            if (e[i].v && h[e[i].to] < 0)

            {

                q[w++] = e[i].to;

                h[e[i].to] = h[now] + 1;

            }

    }

    if (h[n * m] == -1)

        return 0;

    return 1;

}

int dfs(const int x, const int f)

{

    if (x == n * m)

        return f;

    int w, used = 0;

    for (int i = head[x]; i; i = e[i].nex)

        if (e[i].v && h[e[i].to] == h[x] + 1)

        {

            w = dfs(e[i].to, std::min(w, e[i].v));

            e[i].v -= w;

            e[i + 1].v += w;

            used += w;

            if (used == f)

                return f;

        }

    if (!used)

        h[x] = -1;

//  debug(used);

    return used;

}

void Dinic()

{

    while (bfs())

        ans += dfs(1, INT_MAX);

}

int main(int argc, char ** argv)

{

    n = nextInt();

    m = nextInt();

    int x;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j < m; j++)

        {

            x = nextInt();

            Insert(m * (i - 1) + j, m * (i - 1) + j + 1, x);

            Insert(m * (i - 1) + j + 1, m * (i - 1) + j, x);

        }

    for (int i = 1; i < n; i++)

        for (int j = 1; j <= m; j++)

        {

            x = nextInt();

            Insert(m * (i - 1) + j, m * i + j, x);

            Insert(m * i + j, m * (i - 1) + j, x);

        }

    for (int i = 1; i < n; i++)

        for (int j = 1; j < m; j++)

        {

            x = nextInt();

            Insert(m * (i - 1) + j, m * i + j + 1, x);

            Insert(m * i + j + 1, m * (i - 1) + j, x);

        }

    Dinic();

    std::cout << ans/* << std::endl*/;

#ifdef __NOTEPADPP

    std::cin.get();

    std::cin.get();

#endif

    return 0;

}