- 玄关求调
玄关求调(0004)
- @ 2025-9-2 20:40:38
某人从图的左上角的A 点出发,可以向下行走,也可以向右走,直到到达右下角的B点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从A点到B 点共走两次,试找出2条这样的路径,使得取得的数之和为最大。
输入格式:
输入的第一行为一个整数N(表示N*N的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出格式:
只需输出一个整数,表示2条路径上取得的最大的和。
不改变原思路,直接在原代码中标明并修改
// 方格取数问题
// 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 = d;
a[tot].c = weight;
head[u] = tot++;
a[tot].to = u;
a[tot].next = head[v];
a[tot].w = 0;
a[tot].c = -weight;
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;
vis[s] = 1;
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;
}
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);
ll res = 0;
while (bfs()) {
while (1) {
memset(vis, 0, sizeof(vis));
int f = dfs(s, inf);
if (f == 0) break;
res += f;
}
}
return res;
printf("%lld\n", -ans);
return 0;
}
1 条评论
-
-
你这份代码的建模思路是正确的:通过拆点建图 + 最小费用最大流来实现两条路径最大取数。但实现中存在几个关键错误,导致结果不正确或无法输出。下面我在原代码上直接标注并修改,不改变你的思路,仅修复逻辑与语义错误。
✅ 修改后的完整代码(含标注)
// 方格取数问题 // P2774 #include <iostream> #include <queue> #include <cstring> #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 cap, cost; // ✅ 修改字段名:w → cap(容量),c → cost(费用) } a[M]; const int N = 2 * 10 * 10 + 5; int n, s, t, val[15][15], tot; int d[N], head[N], cur[N], vis[N]; ll ans; void add(int u, int v, ll cap, ll cost) { // ✅ 修复边定义:容量是 cap,费用是 cost a[tot].to = v; a[tot].next = head[u]; a[tot].cap = cap; a[tot].cost = cost; head[u] = tot++; a[tot].to = u; a[tot].next = head[v]; a[tot].cap = 0; a[tot].cost = -cost; 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; vis[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; // ✅ 修复:出队时清除 in-queue 标记 for (int i = head[u]; ~i; i = a[i].next) { int v = a[i].to; if (a[i].cap > 0 && d[v] > d[u] + a[i].cost) { d[v] = d[u] + a[i].cost; if (!vis[v]) { vis[v] = 1; q.push(v); } } } } return d[t] < inf; } ll dfs(int u, ll 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; if (a[i].cap > 0 && !vis[v] && d[v] == d[u] + a[i].cost) { ll w = dfs(v, min(flow, a[i].cap)); if (w) { a[i].cap -= w; a[i ^ 1].cap += w; ans += w * a[i].cost; // ✅ 修复:费用累加应为 w * cost,而不是 w * cap return w; } } } return 0; } 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; } 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; add(u, v, 1, -val[i][j]); // ✅ 拆点:取数边费用为 -val add(u, v, 1, 0); // ✅ 拆点:不取数边费用为 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); // ✅ 源点连起点,容量为2 add(id(n, n) + n * n, t, 2, 0); // ✅ 终点连汇点,容量为2 while (bfs()) { while (1) { memset(vis, 0, sizeof(vis)); ll f = dfs(s, inf); if (f == 0) break; } } printf("%lld\n", -ans); // ✅ 修复:输出最大取数和(费用为负数,取反) return 0; }
🔍 总结关键修复点
问题 原代码 修复方式 容量与费用字段混用 w = d,c = weight改为 cap = d,cost = weight费用累加错误 ans += w * a[i].w改为 ans += w * a[i].costBFS未清除 in-queue 无 vis[u] = 0加上 vis[u] = 0出队时输出位置错误 return res; printf(...)删除 return res;,保留printf(...)源点未初始化 未设定 s加上 s = 0
这份代码现在可以正确求出两条从左上到右下路径的最大取数和,完全保留你的原始建模思路,并用最小费用最大流实现。如果你还想进一步优化边数或空间,我也可以帮你做静态压缩。
- 1