1744: 方格取数问题——最小割

1744: 方格取数问题——最小割

题意：

在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任 意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。 编程任务： 对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

思路：

首先对矩阵进行黑白点染色， 相邻的两个点颜色不同。然后每个黑点向四周连有向边，容量为INF， 之后源点向黑点连有向边，容量为点权，白点向汇点连边，容量为点权。然后跑最小割，用所有点权之和减最小割即可。

#include #include #include #include #include #include using namespace std;const int maxn = 1000;const int INF = 0x3f3f3f3f;const int dx[] = {0, 0, -1, 1};const int dy[] = {-1, 1, 0, 0};struct Edge { int from, to, cap, flow;};struct Dinic { int s, t; vector edges; vector G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void init() { edges.clear(); for (int i = 0; i < maxn; i++) G[i].clear(); } void addedge(int from, int to, int cap) { edges.push_back(Edge{from, to, cap, 0}); edges.push_back(Edge{to, from, 0, 0}); int x = edges.size(); G[from].push_back(x-2); G[to].push_back(x-1); } bool bfs() { memset(vis, 0, sizeof(vis)); queue q; q.push(s); d[s] = 0; vis[s] = 1; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; q.push(e.to); } } } return vis[t]; } int dfs(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i < G[x].size(); i++) { Edge &e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int maxflow(int s, int t) { this->s = s, this->t = t; int flow = 0; while (bfs()) { memset(cur, 0, sizeof(cur)); flow += dfs(s, INF); } return flow; }}ac;int a[100][100], flag[100][100];int main() { int m, n; scanf("%d%d", &m, &n); int s = 0, t = m*n + 1; int sum = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &a[i][j]); sum += a[i][j]; } } memset(flag, 0, sizeof(flag)); int f; for (int i = 1; i <= m; i++) { f = i & 1; for (int j = 1; j <= n; j++) { flag[i][j] = f; f ^= 1; } } //build for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (flag[i][j] == 0) continue; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (1 <= x && x <= m && 1 <= y && y <= n) { ac.addedge(n*(i-1)+j, n*(x-1)+y, INF); } } } } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (flag[i][j] == 1) ac.addedge(s, n*(i-1)+j, a[i][j]); else ac.addedge(n*(i-1)+j, t, a[i][j]); } } printf("%d\n", sum - ac.maxflow(s, t)); return 0;}/*3 31 2 33 2 32 3 1*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。