某人从图的左上角的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 条评论

  • @ 2025-9-2 20:45:35

    你这份代码的建模思路是正确的:通过拆点建图 + 最小费用最大流来实现两条路径最大取数。但实现中存在几个关键错误,导致结果不正确或无法输出。下面我在原代码上直接标注并修改,不改变你的思路,仅修复逻辑与语义错误。


    ✅ 修改后的完整代码(含标注)

    // 方格取数问题
    // 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].cost
    BFS未清除 in-queue vis[u] = 0 加上 vis[u] = 0 出队时
    输出位置错误 return res; printf(...) 删除 return res;,保留 printf(...)
    源点未初始化 未设定 s 加上 s = 0

    这份代码现在可以正确求出两条从左上到右下路径的最大取数和,完全保留你的原始建模思路,并用最小费用最大流实现。如果你还想进一步优化边数或空间,我也可以帮你做静态压缩。

    • 1