#include <bits/stdc++.h>
using namespace std;

const int N = 910, D[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const int inf = 1 << 30;
int n, m, s, t, cur[N], q[N], a[33][33];
int e[N][N], dis[N];

int id(int x, int y) {
    return (x - 1) * m + y;
}

bool bfs() {
    memset(dis, 0, sizeof(dis));
    for (int i = 1; i <= n; i++) cur[i] = 1;
    int front = 1, rear = 0;
    q[++rear] = s;
    dis[s] = 1;
    while (front <= rear) {
        int u = q[front++];
        if (u == t) break;
        for (int v = 1; v <= n; v++)
            if (e[u][v] > 0 && !dis[v]) {
                dis[v] = dis[u] + 1;
                q[++rear] = v;
            }
    }
    return dis[t];
}

int dfs(int u, int flow) {
    if (u == t) return flow;
    int res = 0;
    for (int v = cur[u]; v <= n && flow; v++) {
        cur[u] = v;
        if (e[u][v] > 0 && dis[v] == dis[u] + 1) {
            int c = dfs(v, min(e[u][v], flow));
            e[u][v] -= c;
            e[v][u] += c;
            flow -= c;
            res += c;
        }
    }
    if (!res) dis[u] = 0;
    return res;
}

int dinic() {
    int maxflow = 0;
    while (bfs()) {
        maxflow += dfs(s, inf);
    }
    return maxflow;
}

int main() {
    scanf("%d%d", &n, &m);
    int sm = 0;
    int s = 0, t = n * m + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]), sm += a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 4; k++) {
                int x = i + D[k][0], y = j + D[k][1];
                if (x < 1 || x > n || y < 1 || y > m) continue;
                e[id(i, j)][id(x, y)] = inf;
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if ((i + j) % 2 == 0)
                e[s][id(i, j)] = a[i][j];
            else
                e[id(i, j)][t] = a[i][j];
    n = n * m + 1;
    printf("%d\n", sm - dinic());
}

在一个有 m×n 个方格的棋盘中,每个方格中有一个正整数。 现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。

输入格式:

第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。

注意m 是行数,n是列数。

输出格式:

输出取数的最大总和。

限制:

1≤n,m≤30

样例 1 :

输入: 3 3 1 2 3 3 2 3 2 3 1

输出: 11

样例 2 :

输入: 3 3 100 1 2 3 4 100 100 5 6

输出: 300

1 条评论

  • @ 2025-9-3 11:22:11

    我看出来你贴的这段代码是想用 最大流 / 最小割 来解这个“棋盘取数”问题,但它现在有几个关键问题,导致结果不一定正确,甚至可能直接运行出错。
    我帮你梳理一下原理、问题和修正方法。


    1. 问题本质

    题目要求:

    • 棋盘上选一些格子上的数,使得任意两个被选格子不相邻(上下左右不接触)
    • 选出的数字和最大

    这是一个 棋盘上的最大权独立集 问题。
    对于二分图(棋盘黑白染色后相邻格子必然一黑一白),有经典结论:

    最大权独立集权值 = 总权值和 − 最小权点覆盖权值

    最小权点覆盖 可以通过 最小割 求出:

    • 把棋盘黑白染色((i+j) 偶数为黑,奇数为白)
    • 从源点连向黑格,容量为该格权值
    • 白格连向汇点,容量为该格权值
    • 黑格与相邻白格之间连容量为 ∞ 的边
    • 最小割的值就是最小权点覆盖
    • 答案 = 总和 − 最小割

    2. 你代码里的主要问题

    (1) 全局变量 nmst 混乱

    你在 main 里又定义了 int s = 0, t = n*m+1;
    这会屏蔽掉全局的 st,导致 bfs()dfs() 用的 st 其实是全局未赋值的版本。
    同样,n 在建图后被改成 n*m+1,这会影响 id() 计算,因为 id() 用的 m 是列数,但 n 已经被改了。

    修正

    • rowscols 存原始行列数
    • 单独用 tot = rows * cols 表示格子数
    • 源点 S = 0,汇点 T = tot + 1
    • 最大流里用 nodeCount = T 表示总节点数(1-based 到 T)

    (2) Dinic 实现细节

    • cur[] 应该存的是当前弧的 邻接表下标,而不是节点编号(你现在是邻接矩阵写法,效率低且容易错)
    • 你用 e[N][N] 存容量,空间是 910×910,虽然能放下 30×30 棋盘,但效率很差
    • BFS/DFS 里循环到 n,但 n 被改成了 n*m+1,含义混乱

    (3) 建图顺序

    正确顺序应该是:

    1. 读入 rowscols
    2. 计算 tot = rows * cols
    3. S = 0T = tot + 1
    4. 黑格:S -> id(i,j) 容量 = a[i][j]
    5. 白格:id(i,j) -> T 容量 = a[i][j]
    6. 黑格与相邻白格:容量 = ∞
    7. 跑最大流
    8. 答案 = sum − maxflow

    3. 修正版核心代码(保持你极简风格)

    #include <bits/stdc++.h>
    using namespace std;
    const int INF = 1<<30;
    const int D[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
    int rows, cols, S, T, tot;
    int a[35][35], cap[1000][1000], dis[1000], cur[1000], q[1000];
    
    int id(int x,int y){ return (x-1)*cols + y; }
    
    bool bfs(){
        memset(dis,0,sizeof(dis));
        dis[S]=1; int l=0,r=0; q[r++]=S;
        while(l<r){
            int u=q[l++];
            for(int v=0;v<=T;v++)
                if(cap[u][v]>0 && !dis[v]){
                    dis[v]=dis[u]+1;
                    q[r++]=v;
                }
        }
        return dis[T];
    }
    
    int dfs(int u,int f){
        if(u==T) return f;
        int res=0;
        for(int &v=cur[u];v<=T && f;v++){
            if(cap[u][v]>0 && dis[v]==dis[u]+1){
                int c=dfs(v,min(cap[u][v],f));
                cap[u][v]-=c; cap[v][u]+=c;
                f-=c; res+=c;
            }
        }
        if(!res) dis[u]=0;
        return res;
    }
    
    int dinic(){
        int flow=0;
        while(bfs()){
            for(int i=0;i<=T;i++) cur[i]=0;
            flow+=dfs(S,INF);
        }
        return flow;
    }
    
    int main(){
        scanf("%d%d",&rows,&cols);
        tot=rows*cols; S=0; T=tot+1;
        int sum=0;
        for(int i=1;i<=rows;i++)
            for(int j=1;j<=cols;j++){
                scanf("%d",&a[i][j]);
                sum+=a[i][j];
            }
        for(int i=1;i<=rows;i++)
            for(int j=1;j<=cols;j++){
                if((i+j)%2==0){
                    cap[S][id(i,j)]=a[i][j];
                    for(int k=0;k<4;k++){
                        int x=i+D[k][0], y=j+D[k][1];
                        if(x>=1 && x<=rows && y>=1 && y<=cols)
                            cap[id(i,j)][id(x,y)]=INF;
                    }
                }else cap[id(i,j)][T]=a[i][j];
            }
        printf("%d\n",sum - dinic());
    }
    

    4. 复杂度

    • 节点数 ≤ 902(30×30 + S + T)
    • 边数 ≤ 4×格子数 + 格子数 + 格子数 ≈ O(nm)
    • Dinic 在这种稠密度下能轻松跑过

    如果你愿意,我可以帮你把这个版本改成 邻接表 + Dinic,这样会更快更优雅,而且不会有 O(V^2) 的矩阵循环浪费。
    你要我帮你改成邻接表版本吗?这样代码会更贴近竞赛模板。

    • 1