之前这个板子使用的都没问题,今天在这道题目上却出了问题,目前不知道是什么原因。
#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;
}