- 玄关求调
1234567890
- @ 2025-9-3 11:20:26
#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 条评论
-
-
我看出来你贴的这段代码是想用 最大流 / 最小割 来解这个“棋盘取数”问题,但它现在有几个关键问题,导致结果不一定正确,甚至可能直接运行出错。
我帮你梳理一下原理、问题和修正方法。
1. 问题本质
题目要求:
- 棋盘上选一些格子上的数,使得任意两个被选格子不相邻(上下左右不接触)
- 选出的数字和最大
这是一个 棋盘上的最大权独立集 问题。
对于二分图(棋盘黑白染色后相邻格子必然一黑一白),有经典结论:最大权独立集权值 = 总权值和 − 最小权点覆盖权值
而 最小权点覆盖 可以通过 最小割 求出:
- 把棋盘黑白染色((i+j) 偶数为黑,奇数为白)
- 从源点连向黑格,容量为该格权值
- 白格连向汇点,容量为该格权值
- 黑格与相邻白格之间连容量为 ∞ 的边
- 最小割的值就是最小权点覆盖
- 答案 = 总和 − 最小割
2. 你代码里的主要问题
(1) 全局变量
n、m、s、t混乱你在
main里又定义了int s = 0, t = n*m+1;,
这会屏蔽掉全局的s、t,导致bfs()、dfs()用的s、t其实是全局未赋值的版本。
同样,n在建图后被改成n*m+1,这会影响id()计算,因为id()用的m是列数,但n已经被改了。修正:
- 用
rows、cols存原始行列数 - 单独用
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) 建图顺序
正确顺序应该是:
- 读入
rows、cols - 计算
tot = rows * cols S = 0,T = tot + 1- 黑格:
S -> id(i,j)容量 = a[i][j] - 白格:
id(i,j) -> T容量 = a[i][j] - 黑格与相邻白格:容量 = ∞
- 跑最大流
- 答案 = 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