60pts,非讨论版问题,求助
  • 板块P4313 文理分科
  • 楼主yyyx_0x1631c
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/25 12:00
  • 上次更新2025/1/25 16:34:17
查看原帖
60pts,非讨论版问题,求助
844951
yyyx_0x1631c楼主2025/1/25 12:00
#include <bits/stdc++.h>
#include <bits/extc++.h>

char yyyx[1 << 20], *yx, *xy;
#define getchar() (yx == xy && (xy = (yx = yyyx) + fread(yyyx, 1, 1 << 20, stdin), yx == xy) ? 0 : *yx++)

template <typename T>
inline void read(T &x)
{
    x = 0;
    register char c = getchar();
    register short f = 1;
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}

template <typename T, typename... Args>
inline void read(T &x, Args &...temps)
{
    read(x), read(temps...);
}
using namespace std;

const int N = 1e6 + 5;
typedef long long ll;

int n, m, s, t;
int box[N], to[N], nxt[N], tot = 1;
ll val[N];

void add_edge(int x, int y, ll w)
{
    nxt[++tot] = box[x];
    to[tot] = y;
    val[tot] = w;
    box[x] = tot;
}

int dep[2005], res[2005];

bool bfs()
{
    queue<int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1;
    q.emplace(s);
    res[s] = box[s];
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = box[x]; ~i; i = nxt[i])
        {
            int y = to[i];
            ll w = val[i];
            if (!dep[y] && w)
            {
                res[y] = box[y];
                dep[y] = dep[x] + 1;
                if (y == t)
                    return 1;
                q.emplace(y);
            }
        }
    }
    return dep[t];
}

ll dfs(int x, ll flow)
{
    if (x == t)
        return flow;
    ll cnt = 0;
    for (int i = res[x]; ~i && flow; i = nxt[i])
    {
        res[x] = i;
        int y = to[i];
        ll w = val[i];
        if (dep[y] != dep[x] + 1 || !w)
            continue;
        ll fw = dfs(y, min(w, flow));
        if (fw)
        {
            dep[y] = 0;
            val[i] -= fw;
            val[i ^ 1] += fw;
            cnt += fw;
            flow -= fw;
        }
    }
    return cnt;
}

ll dinic()
{
    int ans = 0;
    while (bfs())
        ans += dfs(s, 1e16);
    return ans;
}

int pt(int x, int y)
{
    return (x - 1) * m + y;
}

void solve(int f, int x, int y, bool tp)
{
    if (!tp)
    {
        if (x > 1)
        {
            add_edge(f, pt(x - 1, y), 1e9);
            add_edge(pt(x - 1, y), f, 0);
        }
        if (x < n)
        {
            add_edge(f, pt(x + 1, y), 1e9);
            add_edge(pt(x + 1, y), f, 0);
        }
        if (y > 1)
        {
            add_edge(f, pt(x, y - 1), 1e9);
            add_edge(pt(x, y - 1), f, 0);
        }
        if (y < m)
        {
            add_edge(f, pt(x, y + 1), 1e9);
            add_edge(pt(x, y + 1), f, 0);
        }
    }
    else
    {
        if (x > 1)
        {
            add_edge(pt(x - 1, y), f, 1e9);
            add_edge(f, pt(x - 1, y), 0);
        }
        if (x < n)
        {
            add_edge(pt(x + 1, y), f, 1e9);
            add_edge(f, pt(x + 1, y), 0);
        }
        if (y > 1)
        {
            add_edge(pt(x, y - 1), f, 1e9);
            add_edge(f, pt(x, y - 1), 0);
        }
        if (y < m)
        {
            add_edge(pt(x, y + 1), f, 1e9);
            add_edge(f, pt(x, y + 1), 0);
        }
    }
}

signed main()
{
    memset(box, -1, sizeof box);
    read(n, m);
    s = 0;
    t = n * m + 1;
    ll sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1, x; j <= m; j++)
        {
            read(x), sum += x;
            add_edge(s, pt(i, j), x);
            add_edge(pt(i, j), s, 0);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1, x; j <= m; j++)
        {
            read(x), sum += x;
            add_edge(pt(i, j), t, x);
            add_edge(t, pt(i, j), 0);
        }
    int pts = t;
    for (int i = 1; i <= n; i++)
        for (int j = 1, x; j <= m; j++)
        {
            read(x), ++pts, sum += x;
            add_edge(s, pts, x);
            add_edge(pts, s, 0);
            add_edge(pts, pt(i, j), 1e9);
            add_edge(pt(i, j), pts, 0);
            solve(pts, i, j, 0);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1, x; j <= m; j++)
        {
            read(x), ++pts, sum += x;
            add_edge(pts, t, x);
            add_edge(t, pts, 0);
            add_edge(pt(i, j), pts, 1e9);
            add_edge(pts, pt(i, j), 0);
            solve(pts, i, j, 1);
        }
    printf("%lld\n", sum - dinic());

    return 0;
}

2025/1/25 12:00
加载中...