- 玄关求调
玄关求调0005
-
tiangeyuan2025 LV 2 @ 2025-9-3 10:54:39
在一个有 m×n 个方格的棋盘中，每个方格中有一个正整数。 现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
输入格式:
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
注意m 是行数，n是列数。
输出格式:
输出取数的最大总和。
限制:
1≤n,m≤30
修改代码，c++14
// 方格取数2
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define getid(i, j) (i * (n - 1)) + j
using namespace std;
int n, m, s, t, val[105][105], head[105], d[105], sum;
vector<pair<int, int>> a[105];
bool bfs() {
queue<int> q;
q.push(s);
memset(d, 0, sizeof(d));
d[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == t) return 1;
for (auto it : a[u]) {
int v = it.first, w = it.second;
if (!d[v] && w > 0) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[n];
}
int dfs(int u, int flow) {
if (u == t) return flow;
for (int &i = head[u]; i < a[u].size(); i++) {
auto &it = a[u][i];
int v = it.first, &w = it.second;
if (d[v] == d[u] + 1 && w > 0) {
int f = dfs(v, min(flow, w));
if (f > 0) {
w -= f;
for (auto &v_it : a[v]) {
if (v_it.first == u) {
v_it.second += f;
break;
}
}
return f;
}
}
}
return 0;
}
int dinic() {
int ans = 0, flow;
while (bfs()) {
memset(head, 0, sizeof(head));
while (flow = dfs(s, inf))
ans += flow;
}
return ans;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> val[i][j];
sum += val[i][j];
}
}
s = 0, t = n * m + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int id = getid(i, j);
if ((i + j) % 2) {
a[s].push_back({id, val[i][j]});
if (i > 1) a[id].push_back({id - m, inf});
if (j > 1) a[id].push_back({id - 1, inf});
if (i < n) a[id].push_back({id + m, inf});
if (j < m) a[id].push_back({id + 1, inf});
} else
a[id].push_back({t, val[i][j]});
}
}
printf("%d\n", sum - dinic());
return 0;
}
3 条评论
-
-
你这段代码已经非常接近完美地解决了“棋盘取数不相邻最大和”问题，通过构造一个二分图并使用最大流算法（Dinic）求解最大权独立集。👍
不过你提到要“修改代码”，结合 C++14 和题目格式要求，我做了以下几点优化和修正：
✅ 修改点说明：
- 变量命名统一：题目中是
m行n列，但原代码中n是行数，m是列数，容易混淆。已统一为m行，n列。 - 输入格式调整：确保输入顺序与题目一致。
- 边界处理更清晰：邻接边构造部分更易读。
- 代码风格优化：符合 C++14，简洁紧凑，避免冗余。
✅ 修改后的完整代码（C++14）：
#include <iostream> #include <vector> #include <queue> #include <cstring> #define INF 0x3f3f3f3f using namespace std; int m, n, s, t, sum; int val[35][35], head[2005], level[2005]; vector<pair<int, int>> adj[2005]; inline int getid(int i, int j) { return (i - 1) * n + j; } void add(int u, int v, int w) { adj[u].emplace_back(v, w); adj[v].emplace_back(u, 0); } bool bfs() { memset(level, 0, sizeof(level)); queue<int> q; q.push(s); level[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (auto &[v, cap] : adj[u]) { if (!level[v] && cap > 0) { level[v] = level[u] + 1; q.push(v); } } } return level[t]; } int dfs(int u, int flow) { if (u == t) return flow; for (int &i = head[u]; i < adj[u].size(); ++i) { auto &[v, cap] = adj[u][i]; if (level[v] == level[u] + 1 && cap > 0) { int f = dfs(v, min(flow, cap)); if (f > 0) { cap -= f; for (auto &back : adj[v]) { if (back.first == u) { back.second += f; break; } } return f; } } } return 0; } int dinic() { int maxflow = 0, flow; while (bfs()) { memset(head, 0, sizeof(head)); while ((flow = dfs(s, INF)) > 0) maxflow += flow; } return maxflow; } int main() { cin >> m >> n; sum = 0; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) { cin >> val[i][j]; sum += val[i][j]; } s = 0, t = m * n + 1; for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) { int id = getid(i, j); if ((i + j) % 2 == 0) { add(s, id, val[i][j]); if (i > 1) add(id, getid(i - 1, j), INF); if (j > 1) add(id, getid(i, j - 1), INF); if (i < m) add(id, getid(i + 1, j), INF); if (j < n) add(id, getid(i, j + 1), INF); } else { add(id, t, val[i][j]); } } cout << sum - dinic() << '\n'; return 0; }
✅ 核心思路简述：
- 将棋盘建成一个二分图：黑白染色
(i+j)%2。 - 黑点连源点，白点连汇点。
- 黑白之间连边表示不能同时选。
- 最大权独立集 = 总和 - 最大流。
如果你还想进一步优化性能、支持更大规模、或用其他算法（比如状压DP），我也可以帮你拓展。继续深入吗？
- 变量命名统一：题目中是
-
在一个有 m×n 个方格的棋盘中，每个方格中有一个正整数。 现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
输入格式:
第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。
注意m 是行数，n是列数。
输出格式:
输出取数的最大总和。
限制:
1≤n,m≤30
修改代码，c++14
// 方格取数2 #include <iostream> #include <cstring> #include <queue> #include <vector> #define inf 0x3f3f3f3f using namespace std; int n, m, s, t, val[35][35], head[2005], d[2005], sum; vector<pair<int, int>> a[2005]; inline int getid(int i, int j) { return (i - 1) * n + j; } bool bfs() { queue<int> q; q.push(s); memset(d, 0, sizeof(d)); d[s] = 1; while (!q.empty()) { int u = q.front(); q.pop(); if (u == t) return 1; for (auto it : a[u]) { int v = it.first, w = it.second; if (!d[v] && w > 0) { d[v] = d[u] + 1; q.push(v); } } } return d[t]; } int dfs(int u, int flow) { if (u == t) return flow; for (int &i = head[u]; i < a[u].size(); i++) { auto &it = a[u][i]; int v = it.first, &w = it.second; if (d[v] == d[u] + 1 && w > 0) { int f = dfs(v, min(flow, w)); if (f > 0) { w -= f; for (auto &v_it : a[v]) { if (v_it.first == u) { v_it.second += f; break; } } return f; } } } return 0; } int dinic() { int ans = 0, flow; while (bfs()) { memset(head, 0, sizeof(head)); while (flow = dfs(s, inf)) ans += flow; } return ans; } void add(int u, int v, int w) { a[u].push_back({v, w}); a[v].push_back({u, 0}); } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> val[i][j]; sum += val[i][j]; } } s = 0, t = n * m + 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int id = getid(i, j); if ((i + j) % 2) { add(s, id, val[i][j]); if (i > 1) add(id, getid(i - 1, j), inf); if (j > 1) add(id, getid(i, j - 1), inf); if (i < n) add(id, getid(i + 1, j), inf); if (j < m) add(id, getid(i, j + 1), inf); } else add(id, t, val[i][j]); } } cout << sum - dinic() << '\n'; return 0; } -
我看了你的代码，主要问题有两个：
-
m、n 的含义和输入顺序
题目里 m 是行数，n 是列数，但你cin >> n >> m;读反了，而且后续循环和getid宏的计算也混乱。 -
点编号公式错误
你用的#define getid(i, j) (i * (n - 1)) + j是错的，应该是(i - 1) * n + j，这样才能保证二维坐标映射到唯一的 1…m×n 编号。
另外 BFS 返回值和
d[n]也错了，应该判断d[t]是否非零。下面是我帮你改好的 C++14 版本，保持你的 Dinic 思路，但修正了编号、输入顺序、建图逻辑和 BFS 返回值：
#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int m, n, s, t; int val[35][35], sum; vector<pair<int,int>> g[2005]; int d[2005], head[2005]; inline int getid(int i, int j) { return (i - 1) * n + j; } bool bfs() { queue<int> q; memset(d, 0, sizeof(d)); d[s] = 1; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (auto &e : g[u]) { int v = e.first, w = e.second; if (!d[v] && w > 0) { d[v] = d[u] + 1; q.push(v); } } } return d[t] != 0; } int dfs(int u, int flow) { if (u == t) return flow; for (int &i = head[u]; i < (int)g[u].size(); i++) { auto &e = g[u][i]; int v = e.first, &w = e.second; if (d[v] == d[u] + 1 && w > 0) { int f = dfs(v, min(flow, w)); if (f > 0) { w -= f; for (auto &rev : g[v]) { if (rev.first == u) { rev.second += f; break; } } return f; } } } return 0; } int dinic() { int ans = 0, flow; while (bfs()) { memset(head, 0, sizeof(head)); while ((flow = dfs(s, INF)) > 0) ans += flow; } return ans; } void add_edge(int u, int v, int w) { g[u].push_back({v, w}); g[v].push_back({u, 0}); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> m >> n; // m 行, n 列 sum = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> val[i][j]; sum += val[i][j]; } } s = 0; t = m * n + 1; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { int id = getid(i, j); if ((i + j) % 2 == 0) { add_edge(s, id, val[i][j]); if (i > 1) add_edge(id, getid(i - 1, j), INF); if (j > 1) add_edge(id, getid(i, j - 1), INF); if (i < m) add_edge(id, getid(i + 1, j), INF); if (j < n) add_edge(id, getid(i, j + 1), INF); } else { add_edge(id, t, val[i][j]); } } } cout << sum - dinic() << "\n"; return 0; }改动要点
- 输入顺序：
cin >> m >> n;保证 m 是行数，n 是列数。 - 编号公式：
(i - 1) * n + j，编号范围 1…m×n。 - BFS 返回值：判断
d[t]而不是d[n]。 - 建图：用
add_edge同时加正反边，方便反向流更新。 - 容量：黑白染色法，(i+j) 偶数连源点，奇数连汇点，偶数格向相邻奇数格连容量 INF。
这样就能正确求出最大权独立集的权值，输出即为最大取数和。
如果你愿意，我还可以帮你画出这个棋盘的黑白染色示意图，方便理解为什么这是一个二分图最大权独立集问题。这样你会更直观地看到 Dinic 在这里的作用。你要看吗？
-
- 1