题目链接：HDU-3338 Kakuro Extension
题意
给出一个$n imes m$的网格，每个格子为黑色或白色，对于一行中连续的若干个白色格子，我们要往这若干个白色格子中填入$1sim 9$的数字，使其和等于左边黑色格子中的一个已知数字$a_1$；对于一列中连续的若干个白色格子，同理填入$1sim 9$的数字使其和等于上边黑色格子中的一个已知数字$a_2$。如果一个黑色格子相邻的右边和下边都有白色格子，那么这个黑色格子是带有两个已知数字$a_1$和$a_2$的，分别代表右边和下边白色格子的和。要求给出所有白色格子的填数方案。
思路
抽象出源点$s$和汇点$t$，下面用(始点，终点，容量)来表示流网络中的一条边，建图：
对于带有$a_1$的黑色格子$u$，连边$(s, u, a_1-cnt_1)$（$cnt_1$表示$u$右边相邻连续的白色格子数量）；
对于带有$a_2$的黑色格子$u'$，连边$(u',t,a_2-cnt_2)$（$cnt_2$表示$u$下边相邻连续的白色格子数量）；
对于带有$a_1$和$a_2$的黑色格子，则需要拆成两个点$u$和$u'$，连边$(s, u, a_1-cnt_1)$，$(u',t,a_2-cnt_2)$；
对于白色格子$v$的连边，由于填入的数字有$1sim 9$的限制，是有上下界限制的网络流，我们用边$(v,u')$的流量来表示填入的数字，因为最大流中有的边流量可能为$0$，所以我们将$1sim 9$的限制改为$0sim 8$，最后输出的时候再加$1$即可(这也是为什么上面的连边都要减掉$cnt_1$或$cnt_2$，因为每个格子数字减了$1$，总和就要减掉格子数量)，这样我们应该连的边为$(u, v, 8), (v, u', 8)$。
Ford-Fulkerson方法跑最大流后，边$(v,u')$的初始容量$8$减去残余容量就是这条边的流量，再$+1$就是$v$对应的白色格子应填入的数字。
实际实现中，用合理的编号表示上面所提到的$u,u',v$等结点，不要不同结点用相同编号即可。
代码实现
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using std::queue; const int INF = 0x3f3f3f3f, N = 22000, M = 55000; int head[N], d[N]; int s, t, tot, maxflow; struct Edge { int to, cap, nex; } edge[M]; struct Grid { int x, y; bool color; } grid[110][110]; queue<int> q; void add(int x, int y, int z) { edge[++tot].to = y, edge[tot].cap = z, edge[tot].nex = head[x], head[x] = tot; edge[++tot].to = x, edge[tot].cap = 0, edge[tot].nex = head[y], head[y] = tot; } bool bfs() { memset(d, 0, sizeof(d)); while (q.size()) q.pop(); q.push(s); d[s] = 1; while (q.size()) { int x = q.front(); q.pop(); for (int i = head[x]; i; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && !d[v]) { q.push(v); d[v] = d[x] + 1; if (v == t) return true; } } } return false; } int dinic(int x, int flow) { if (x == t) return flow; int rest = flow, k; for (int i = head[x]; i && rest; i = edge[i].nex) { int v = edge[i].to; if (edge[i].cap && d[v] == d[x] + 1) { k = dinic(v, std::min(rest, edge[i].cap)); if (!k) d[v] = 0; edge[i].cap -= k; edge[i^1].cap += k; rest -= k; } } return flow - rest; } void init(int n) { tot = 1, maxflow = 0; s = n + 1, t = s + 1; memset(head, 0, sizeof(head)); } void read_build(int n, int m) { char str[10]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf(" %s", str); if (str[0] == '.') { grid[i][j].color = grid[i][j].x = grid[i][j].y = 0; continue; } grid[i][j].color = 1; if (str[0] != 'X') grid[i][j].y = (str[0] - '0') * 100 + (str[1] - '0') * 10 + (str[2] - '0'); else grid[i][j].y = 0; if (str[4] != 'X') grid[i][j].x = (str[4] - '0') * 100 + (str[5] - '0') * 10 + (str[6] - '0'); else grid[i][j].x = 0; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int cnt = 0; if (grid[i][j].color && grid[i][j].y) { for (int k = i + 1; k < n; k++) { if (grid[k][j].color) break; ++cnt; add(k * m + j, n * m + i * m + j, 8); } add(n * m + i * m + j, t, grid[i][j].y - cnt); } cnt = 0; if (grid[i][j].color && grid[i][j].x) { for (int k = j + 1; k < m; k++) { if (grid[i][k].color) break; ++cnt; add(i * m + j, i * m + k, 8); } add(s, i * m + j, grid[i][j].x - cnt); } } } } void print(int n, int m) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j].color == 1) { printf("_%c", " "[j==m-1]); continue; } int res = 0; for (int k = head[i*m+j]; k; k = edge[k].nex) { if (k % 2 == 0) res += edge[k].cap; } printf("%d%c", 9 - res, " "[j==m-1]); } } } int main() { int n, m; while (~scanf("%d %d", &n, &m)) { init(2 * n * m); read_build(n, m); while (bfs()) maxflow += dinic(s, INF); print(n, m); } return 0; }