dinic求助T爆了,悬赏lzp香吻一个
  • 板块P4313 文理分科
  • 楼主Catium
  • 当前回复9
  • 已保存回复9
  • 发布时间2022/6/11 22:21
  • 上次更新2023/10/27 23:30:21
查看原帖
dinic求助T爆了,悬赏lzp香吻一个
567054
Catium楼主2022/6/11 22:21
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#ifndef ONLINE_JUDGE
#define DEBUG(A) cout << A << endl
void pre() {
    freopen("in.txt", "r", stdin);
}
#else
void pre() {
    return;
}
#define DEBUG(A)
#endif
const int N = 500500;
struct edge {
    int nxt;
    int v, fl;
};
vector<edge> g;
int head[N];
int tot = 0;
inline void adde(int u, int v, int fl) {
    g.push_back({ head[u], v, fl });
    head[u] = tot++;
}
int dep[N];
bool bfs(int s, int t) {
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s);
    dep[s] = 1;
    while (!q.empty()) {
        // DEBUG("bfs");
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = g[i].nxt) {
            int v = g[i].v;
            int fl = g[i].fl;
            if (dep[v] == 0 && fl != 0) {
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    return dep[t] != 0;
}
int dfs(int u, int in, int t) {
    if (u == t) {
        return in;
    }
    int out = 0;
    for (int i = head[u]; i != -1 && in != 0; i = g[i].nxt) {
        int v = g[i].v;
        int fl = g[i].fl;
        if (dep[v] == dep[u] + 1) {
            int res = dfs(v, min(in, fl), t);
            in -= res;
            out += res;
            g[i].fl -= res;
            g[i ^ 1].fl += res;
        }
    }
    if (out == 0) {
        dep[u] = 0;
    }
    return out;
}
int dinic(int s, int t) {
    int ret = 0;
    while (bfs(s, t)) {
        // DEBUG("dfs");
        ret += dfs(s, 0x3f3f3f3f, t);
    }
    return ret;
}
int n, m;
inline int id(int i, int j, int k) {
    return k * n * m + (i - 1) * m + j;
}
const int fx[5] = { 1, -1, 0, 0, 0 };
const int fy[5] = { 0, 0, 1, -1, 0 };
signed main() {
    pre();
    int sum = 0;
    cin >> n >> m;
    int S = 0;
    int T = 3 * n * m + 1;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tt;
            cin >> tt;
            adde(S, id(i, j, 0), tt);
            adde(id(i, j, 0), S, 0);
            sum += tt;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tt;
            cin >> tt;
            adde(id(i, j, 0), T, tt);
            adde(T, id(i, j, 0), 0);
            sum += tt;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tt;
            cin >> tt;
            adde(S, id(i, j, 1), tt);
            adde(id(i, j, 1), S, 0);
            sum += tt;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tt;
            cin >> tt;
            adde(id(i, j, 2), T, tt);
            adde(T, id(i, j, 2), 0);
            sum += tt;
        }
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int k = 0; k < 5; ++k) {
                int nx = i + fx[k], ny = j + fy[k];
                if (!(nx < 1 || ny < 1 || nx > n || ny > m)) {
                    adde(id(i, j, 1), id(nx, ny, 0), 0x3f3f3f3f);
                    adde(id(nx, ny, 0), id(i, j, 1), 0);
                    adde(id(nx, ny, 0), id(i, j, 2), 0x3f3f3f3f);
                    adde(id(i, j, 2), id(nx, ny, 0), 0);
                }
            }
        }
    }
    cout << sum - dinic(S, T);
    return 0;
}
2022/6/11 22:21
加载中...