求助网络流板子纠错
查看原帖
求助网络流板子纠错
817044
cjwdyzxfblzs楼主2023/10/4 21:36

之前这个板子使用的都没问题,今天在这道题目上却出了问题,目前不知道是什么原因。

#include <bits/stdc++.h>
// #define int long long
inline int rd()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}
const int N = 1e6, inf = 0x3f3f3f3f;
int n, m, s, t, lv[N], cur[N];
int head[N], cnt;
struct Edge {
    int to, w, nxt;
}e[N];
void add(int from, int to, int w) {
    e[cnt] = {to, w, head[from]};
    head[from] = cnt ++ ;
}
void addEdge(int from, int to, int w) {
    add(from, to, w);
    add(to, from, 0);
} 
inline bool bfs()
{
    memset(lv, -1, sizeof(lv));
    lv[s] = 0;
    memcpy(cur, head, sizeof(head));
    std::queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int eg = head[p]; eg; eg = e[eg].nxt)
        {
            int to = e[eg].to, vol = e[eg].w;
            if (vol > 0 && lv[to] == -1)
                lv[to] = lv[p] + 1, q.push(to);
        }
    }
    return lv[t] != -1;
}
int dfs(int p = s, int flow = inf)
{
    if (p == t)
        return flow;
    int rmn = flow;
    for (int eg = cur[p]; eg && rmn; eg = e[eg].nxt)
    {
        cur[p] = eg;
        int to = e[eg].to, vol = e[eg].w;
        if (vol > 0 && lv[to] == lv[p] + 1)
        {
            int c = dfs(to, std::min(vol, rmn));
            if (!c) {
                lv[to] = -1;
                continue;
            }
            rmn -= c;
            e[eg].w -= c;
            e[eg ^ 1].w += c;
        }
    }
    return flow - rmn;
}
inline int Dinic(void)
{
    int ans = 0;
    while (bfs()) 
        ans += dfs();
    return ans;
}
#define code(i, j) (((i) - 1) * m + (j))
auto main() -> signed
{
    n = rd(), m = rd(); 
    s = 1, t = code(n, m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m - 1; j ++ )
        {
            int w = rd();
            addEdge(code(i, j), code(i, j + 1), w);
        }
    for (int i = 1; i <= n - 1; i ++ )
        for (int j = 1; j <= m; j ++ ) 
        {
            int w = rd();
            addEdge(code(i, j), code(i + 1, j), w);
        }
    for (int i = 1; i <= n - 1; i ++ )
        for (int j = 1; j <= m - 1; j ++ )
        {
            int w = rd();
            addEdge(code(i, j), code(i + 1, j + 1), w);
        }
    std::cout << Dinic() << std::endl;
    return 0;
}

2023/10/4 21:36
加载中...