讨论详情 - Sanhai

玄关求调
方格取数0002
tiangeyuan2025 LV 2 MOD @ 2025-9-2 17:12:58

设有N*N的方格图(N<=10）,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入格式:

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出格式:

只需输出一个整数，表示2条路径上取得的最大的和。

c++14,在原代码上改写，并用Dinic网络流，不用vector开数组，能优化就优化，但优化不是改成STL模板库，请标出错误和优化及其原因，不要改动原思路代码：

// 方格取数问题
// P2774
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#define id(i, j) (i - 1) * n + j
#define inf 0x3f3f3f3f

using namespace std;

struct Edge {
    int to, next, w, c;
}a[15 << 3];

int n, s, t, val[15][15], tot, vis[15 << 3];
int d[15 << 3], head[15 << 3], cur[15 << 3];

void add(int u, int v, int weight, int d) {
    a[tot].to = v;
    a[tot].next = head[u];
    a[tot].w = weight;
    a[tot].c = d;
    head[u] = tot++;
}

bool bfs() {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memcpy(cur, head, sizeof(head));
	queue<int> q;
	q.push(s);
	d[s] = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == n) return 1;
		for (int i = head[u]; ~i; i = a[i].next) {
            int v = a[i].to, c = a[i].c;
			if (d[v] > d[u] + c && a[i].w > 0) {
				d[v] = d[u] + c;
				if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
			}
		}
	}
	
    return d[t] < inf;
}

int dfs(int u, int flow) {
	if (u == t) return flow;
    int f = 0;
    vis[u] = 1;

	for (int i = cur[u]; ~i && flow; i = a[i].next) {
        int v = a[i].to, c = a[i].c;
        cur[u] = i;
		if (d[v] == d[u] + c && a[i].w > 0 && !vis[v]) {
            vis[v] = 1;
			int fl = dfs(v, min(flow, a[i].w));
            a[i].w -= c;
            a[i ^ 1].w += c;
            flow -= c;
            f += c;
		}
	}

	if (!f) d[u] = inf;
    return f;
}

int dinic() {
	int ans = 0;
    memset(head, -1, sizeof(head));

	while (bfs()) {
		int flow = dfs(s, inf);
        ans += flow;
    }

	return ans;
}

int main()
{
    scanf("%d", &n);
    int x, y, z;
    while (scanf("%d %d %d", &x, &y, &z) && (x || y || z))
        val[x][y] = z;
    t = 2 * n * n + 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int u = id(i, j), v = u + n * n;
            add(u, v, 1, val[i][j]);
            add(u, v, 1, 0);
            if (j < n) add(v, id(i, j + 1), 2, 0);
            if (i < n) add(v, id(i + 1, j), 2, 0);
        }
    }

    add(s, id(1, 1), 2, 0);
    add(id(n, n) + n * n, t, 2, 0);
    printf("%d\n", dinic());
    return 0;
}

lyx919 V LV 2 MOD @ 2025-9-2 20:22:27

方格取数：网络流建模与修正

你的思路是对的：把每个格子拆点（入点u与出点v=u+n*n），u→v放两条边（1条容量1、费用为−val，一条容量1、费用0），右移/下移边容量为2、费用0，源点s连(1,1)入点，(n,n)出点连汇点t；求从s到t的最小费用最大流，答案取相反数即为两条路拿数的最大和。问题出在实现层面。

关键错误与原因

容量与费用字段混用： add(u,v,d,weight)里将 a[tot].w = weight, a[tot].c = d，导致 w 存的其实是费用、c 才是容量；而 BFS/DFS 中却用 a[i].w 当容量判断和修改，这会把“费用”当“容量”扣减，彻底错乱。
费用累计位置与变量错误： DFS 回溯时用了 ans += w * a[i].w，但 a[i].w 在上一步被当作“容量”扣减了，即便语义对也成了扣减后的值；正确应当累加“边费用 × 流量”。
BFS 写成最短路却缺 in-queue 管理： 这是在跑费用流的最短路（SPFA），但出队时没有 vis[u]=0（即 in-queue 复位），会阻止被多次入队放松，导致最短路不正确或卡死在初次入队状态。
一次 BFS 只增广一次： 你的 dinic() 里每次找完最短路只 DFS 一次就重跑 BFS；应当在同一轮最短路标号下，用 DFS 把所有“可增广的最短路边”尽量送满（多次 DFS 直至无增广）。
函数语义与算法不符： 题目需要“费用流”，单纯 Dinic（仅最大流）不处理费用，无法“最大化取数”。你当前结构是“SPFA + DFS 沿可行边增广”的费用流写法（常见的 ZKW 结构风格），保留这个思路即可正确求解。
距离数组类型与初始化不当： d 用 int + memset 0x3f 不稳妥；费用可能累加，需 long long 距离，且用显式 INF 初始化。
源点未显式初始化： s 依赖全局零初始化虽可用，但应当明确设定 s=0 提升健壮性与可读性。
宏 min 覆盖风险： 自定义宏 min 会造成类型截断与多次求值隐患。这里改为显式分支/标准库最小化，避免再踩坑。

修正后的要点

明确边字段：cap 表容量、cost 表费用。
BFS 用 SPFA 求最短费用势能 d[]，并在出队时清 in-queue。
DFS 仅走满足 d[v] == d[u] + cost 的可行边，送流并累计费用。
在每轮最短路后，用 DFS 循环送尽（直到本轮无流），再重新最短路。
最终答案输出为 -minCost（因为收集边费用是 −val）。

C++14 修正版（保留原思路与静态数组，去除 vector）

// 方格取数问题 最小费用最大流（SPFA + DFS）
// C++14，无 vector，静态数组
#include <bits/stdc++.h>
using namespace std;

#define id(i, j) ((i) - 1) * n + (j)
const int MAXN = 2 * 10 * 10 + 5;     // 节点上限：2*n*n + s,t
const int MAXM = 10000 + 1023;        // 边上限（含反向边）
const long long INFLL = (long long)4e18;

struct Edge {
    int to, next;
    int cap, cost;
} e[MAXM];

int n, s, t, tot;
int head[MAXN], cur[MAXN];
int val[MAXN][MAXN];

long long distv[MAXN];
int inq[MAXN], vis[MAXN];

long long minCost = 0;
int maxFlow = 0;

void addEdge(int u, int v, int cap, int cost) {
    e[tot].to = v; e[tot].next = head[u]; e[tot].cap = cap; e[tot].cost = cost; head[u] = tot++;
    e[tot].to = u; e[tot].next = head[v]; e[tot].cap = 0;   e[tot].cost = -cost; head[v] = tot++;
}

bool spfa() {
    for (int i = 0; i < MAXN; ++i) distv[i] = INFLL, inq[i] = 0;
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    distv[s] = 0; inq[s] = 1; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].to;
            if (e[i].cap > 0 && distv[v] > distv[u] + e[i].cost) {
                distv[v] = distv[u] + e[i].cost;
                if (!inq[v]) { inq[v] = 1; q.push(v); }
            }
        }
    }
    return distv[t] < INFLL;
}

int dfs(int u, int f) {
    if (u == t) return f;
    vis[u] = 1;
    int pushed = 0;
    for (int &i = cur[u]; i != -1 && pushed < f; i = e[i].next) {
        int v = e[i].to;
        if (e[i].cap > 0 && !vis[v] && distv[v] == distv[u] + e[i].cost) {
            int can = f - pushed;
            if (can > e[i].cap) can = e[i].cap;
            int w = dfs(v, can);
            if (w > 0) {
                e[i].cap -= w;
                e[i ^ 1].cap += w;
                minCost += 1LL * w * e[i].cost;
                pushed += w;
            }
        }
    }
    vis[u] = 0;
    return pushed;
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    memset(head, -1, sizeof(head));
    tot = 0;
    int x, y, z;
    while (scanf("%d %d %d", &x, &y, &z) == 3) {
        if (x == 0) break;
        val[x][y] = z;
    }

    s = 0;
    t = 2 * n * n + 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int u = id(i, j), v = u + n * n;
            // 取数边：一次容量1、费用 -val；再给一次容量1、费用0
            addEdge(u, v, 1, -val[i][j]);
            addEdge(u, v, 1, 0);
            // 右移/下移：容量2，费用0
            if (j < n) addEdge(v, id(i, j + 1), 2, 0);
            if (i < n) addEdge(v, id(i + 1, j), 2, 0);
        }
    }

    addEdge(s, id(1, 1), 2, 0);
    addEdge(id(n, n) + n * n, t, 2, 0);

    while (spfa()) {
        while (true) {
            memset(vis, 0, sizeof(vis));
            int f = dfs(s, 1 << 30);
            if (f == 0) break;
            maxFlow += f;
        }
    }

    printf("%lld\n", -minCost);
    return 0;
}

说明与结果

不改变你的建模与思路，仅修正“容量/费用混用、最短路与增广流程、费用统计与数据类型”造成的错误。
算法本质是“费用流”，结构形似 Dinic（分层 + 当前弧 + DFS），对 N≤10 规模足够快。
输出为两条路径可取得的最大和（即最小费用取负值）。

tiangeyuan2025 LV 2 MOD @ 2025-9-2 20:15:22

设有N*N的方格图(N<=10）,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入格式:

输出格式:

只需输出一个整数，表示2条路径上取得的最大的和。

c++14,在原代码上修改，并用Dinic网络流，不用vector开数组，请标出错误及其原因，不要改动原思路代码：

// 方格取数问题
// P2774
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#define id(i, j) (i - 1) * n + j
#define inf 0x3f3f3f3f
#define ll long long
#define min(x, y) (x) < (y) ? (x) : (y)
#define M 10000 + 1023

using namespace std;

struct Edge {
    int to, next;
    ll w, c;
}a[M];

const int N = 2 * 10 * 10 + 5;
int n, s, t, val[N][N], tot, vis[N];
int d[N], head[N], cur[N];
ll ans;

void add(int u, int v, ll d, ll weight) {
    a[tot].to = v;
    a[tot].next = head[u];
    a[tot].w = weight;
    a[tot].c = d;
    head[u] = tot++;
    a[tot].to = u;
    a[tot].next = head[v];
    a[tot].w = -weight;
    a[tot].c = 0;
    head[v] = tot++;
}

bool bfs() {
    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    memcpy(cur, head, sizeof(head));
	queue<int> q;
	q.push(s);
	d[s] = 0;

	while (!q.empty()) {
		int u = q.front();
		q.pop();
		if (u == t) return 1;
		for (int i = head[u]; ~i; i = a[i].next) {
            int v = a[i].to, c = a[i].c;
			if (d[v] > d[u] + c && a[i].w > 0) {
				d[v] = d[u] + c;
				if (!vis[v]) {
                    vis[v] = 1;
                    q.push(v);
                }
			}
		}
	}
	
    return d[t] < inf;
}

ll dfs(int u, int flow) {
	if (u == t) return flow;
    vis[u] = 1;

	for (int i = cur[u]; ~i && flow; i = a[i].next) {
        int v = a[i].to, c = a[i].c;
        cur[u] = i;
		if (d[v] == d[u] + c && a[i].w > 0 && !vis[v]) {
			int w = dfs(v, min(flow, a[i].w));
            if (w) {
                a[i].w -= w;
                a[i ^ 1].w += w;
                ans += w * a[i].w;
                return w;
            }
            
		}
	}

	return 0;
}

ll dinic() {
	ll ans = 0;

	while (bfs()) {
        memset(vis, 0, sizeof(vis));
		ll flow = dfs(s, inf);
        ans += flow;
    }

	return ans;
}

int main()
{
    scanf("%d", &n);
    memset(head, -1, sizeof(head));
    int x, y, z;
    while (scanf("%d %d %d", &x, &y, &z)) {
        if (x == 0) break;
        val[x][y] = z;
    }

    t = 2 * n * n + 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int u = id(i, j), v = u + n * n;
            add(u, v, 1, -val[i][j]);
            add(u, v, 1, 0);
            if (j < n) add(v, id(i, j + 1), 2, 0);
            if (i < n) add(v, id(i + 1, j), 2, 0);
        }
    }

    add(s, id(1, 1), 2, 0);
    add(id(n, n) + n * n, t, 2, 0);
    dinic();
    printf("%lld\n", ans);
    return 0;
}

lyx919 V LV 2 MOD @ 2025-9-2 19:36:47

问题修正与原因

错误1: 在 dinic() 中对 head 执行 memset(-1) 清空了整张图，导致此前建好的边全部丢失。应在建图前一次性初始化，而不是在求流时清空。
错误2: 未建反向边，无法维护残量网络；add 只加了正向边，dfs 中也无合法回退路径。
错误3: dfs 中用 w-=c/c+=c 修改的是“费用”变量而非“流量”，应当用实际增广量 flow 更新容量与反向容量。
错误4: bfs 混用“费用松弛”与 Dinic 分层的语义，且错误地以 u==n 作为到达判定，应判定 t；d/vis 同时承担 in-queue 与 dfs 访问标记，语义冲突。
错误5: s、tot、head 未在建图前正确初始化；Edge 数组容量过小，N=10 时极易越界。
错误6: 输入结束标志为单独一行“0”，原代码按三元组 (x,y,z) 判断会误读结束行。
错误7: 目标是最大化取数之和，需“带权”优化。原代码把 val 当作费用但未取相反数，方向错误；应使用最小费用最大流（将权值取负后最小化），或等价的最大费用流。

优化点与理由

算法选择: 采用 ZKW 最小费用最大流（SPFA 建可行势 + Dinic 风格的 DFS 在零势差边上增广），与原“Dinic + 费用”思路一致，常数小、实现紧凑。
建模优化: 节点拆分 u(in)→v(out)。每格两条边：容量 1、费用 -val（第一次经过计分），容量 1、费用 0（第二次经过不计分）；相邻迁移边容量 2、费用 0；源汇容量 2 保证两条路径。
内存与性能: 全部用静态数组与邻接表，无 vector；自实现环形数组队列替代 STL 队列；cur 当前弧与 vis 剪枝减少无效搜索；边空间充足避免越界。
I/O: 使用 scanf/printf，按题意正确处理“单独 0 结束”。

改写后的代码（C++14，静态数组，ZKW 最小费用最大流）

#include <cstdio>
#include <cstring>

const int NMAX = 10;
const int VMAX = 2 * NMAX * NMAX + 5;
const int EMAX = 10000;
const int INF  = 0x3f3f3f3f;

int n, val[NMAX + 1][NMAX + 1];
int s, t, tot, head[VMAX];
int to[EMAX], cap[EMAX], cost[EMAX], nxt[EMAX];

int dist_[VMAX], inq[VMAX], q[VMAX], vis[VMAX], cur[VMAX];
long long minCost;

inline int id(int i, int j) { return (i - 1) * n + j; }

inline void init_graph() {
    tot = 0;
    std::memset(head, -1, sizeof(head));
}

inline void add_edge(int u, int v, int c, int w) {
    to[tot] = v; cap[tot] = c; cost[tot] = w; nxt[tot] = head[u]; head[u] = tot++;
    to[tot] = u; cap[tot] = 0; cost[tot] = -w; nxt[tot] = head[v]; head[v] = tot++;
}

bool spfa() {
    std::memset(dist_, 0x3f, sizeof(dist_));
    std::memset(inq, 0, sizeof(inq));
    int h = 0, tt = 0;
    dist_[s] = 0; inq[s] = 1; q[tt++] = s;
    while (h != tt) {
        int u = q[h++]; if (h >= VMAX) h = 0;
        inq[u] = 0;
        for (int i = head[u]; i != -1; i = nxt[i]) if (cap[i] > 0) {
            int v = to[i], nd = dist_[u] + cost[i];
            if (nd < dist_[v]) {
                dist_[v] = nd;
                if (!inq[v]) {
                    inq[v] = 1;
                    q[tt++] = v; if (tt >= VMAX) tt = 0;
                }
            }
        }
    }
    return dist_[t] < INF;
}

int dfs(int u, int f) {
    if (u == t) return f;
    vis[u] = 1;
    for (int &i = cur[u]; i != -1; i = nxt[i]) {
        int v = to[i];
        if (cap[i] > 0 && !vis[v] && dist_[v] == dist_[u] + cost[i]) {
            int w = dfs(v, f < cap[i] ? f : cap[i]);
            if (w) {
                cap[i] -= w;
                cap[i ^ 1] += w;
                minCost += 1LL * w * cost[i];
                return w;
            }
        }
    }
    return 0;
}

int min_cost_max_flow(int need) {
    int flow = 0; minCost = 0;
    while (flow < need && spfa()) {
        std::memcpy(cur, head, sizeof(head));
        std::memset(vis, 0, sizeof(vis));
        int pushed;
        while (flow < need && (pushed = dfs(s, need - flow))) flow += pushed;
    }
    return flow;
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    std::memset(val, 0, sizeof(val));
    for (;;) {
        int x; if (scanf("%d", &x) != 1) break;
        if (x == 0) break;
        int y, z; scanf("%d%d", &y, &z);
        val[x][y] = z;
    }

    init_graph();
    int N2 = n * n;
    s = 0; t = 2 * N2 + 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int u = id(i, j), v = u + N2;
            add_edge(u, v, 1, -val[i][j]);
            add_edge(u, v, 1, 0);
            if (j < n) add_edge(v, id(i, j + 1), 2, 0);
            if (i < n) add_edge(v, id(i + 1, j), 2, 0);
        }
    }
    add_edge(s, id(1, 1), 2, 0);
    add_edge(id(n, n) + N2, t, 2, 0);

    min_cost_max_flow(2);
    printf("%d\n", (int)(-minCost));
    return 0;
}

结果与说明

正确性: 负费用建图，跑两单位最小费用流，答案取相反数即两条路径取数最大和；每格最多被计分一次。
复杂度: 点数约 2N²+2 ≤ 202，边数 < 1e4；SPFA+DFS 在该规模下稳定通过。

方格取数0002

3 条评论