题目大意：有一个$n\times m$的棋盘，有的格子是障碍。要选择一些格子来放置士兵，一个空格子里可放一个士兵。希望第$i$行至少放置了$l_i$个士兵, 第$j$列至少放置了$c_j$个士兵。要求使用最少个数的士兵。输出个数。
题解：先考虑无解，只要所有能放士兵的地方都放上了士兵，仍然存在行或列不满足限制条件，即为无解。
逆向思考，把求使用最少的士兵转化为，放满士兵后，最多能删掉多少个士兵。网络流。
给每一行每一列分别建一个点，对于所有非障碍坐标$(x,y)$，从$x$行向$y$列连一条容量为$1$的边，表示可以删除一个士兵。
源点向每一行连边，容量为这一行能删除的士兵个数的最大值（即这一行可以放得士兵数减去这一行需要的士兵数）。
列也是这样。跑最大流，每一个单位的流量表示删除一个士兵，从总士兵个数中删除即可
卡点：无
C++ Code：
#include#include #define maxn 111using namespace std;const int inf = 0x3f3f3f3f;int n, m, k, sum;int l[maxn], c[maxn];int L[maxn], C[maxn];bool v[maxn][maxn];int head[maxn << 1], cnt = 2;struct Edge { int to, nxt, w;} e[maxn * maxn << 1];void add(int a, int b, int c) { e[cnt] = (Edge) {b, head[a], c}; head[a] = cnt; e[cnt ^ 1] = (Edge) {a, head[b], 0}; head[b] = cnt ^ 1; cnt += 2;}inline int min(int a, int b) {return a < b ? a : b;}int st, ed;int d[maxn << 1];int q[maxn << 1], h, t;inline bool bfs() { memset(d, 0, sizeof d); d[q[h = t = 0] =st] = 1; while (h <= t) { int u = q[h++]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (!d[v] && e[i].w) { d[v] = d[u] + 1; q[++t] = v; } } } return d[ed];}int dfs(int x, int low) { if (!low || x == ed) return low; int res = 0, w, v; for (int i = head[x]; i; i = e[i].nxt) { v = e[i].to; if ((d[v] == d[x] + 1) && e[i].w) { w = dfs(v, min(low - res, e[i].w)); e[i].w -= w; e[i ^ 1].w += w; res += w; } } if (!res) d[x] = -1; return res;}void dinic() { int ans = 0; while (bfs()) ans += dfs(st, inf); printf("%d\n", sum - ans);}int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; i++) scanf("%d", &l[i]); for (int i = 1; i <= m; i++) scanf("%d", &c[i]); for (int i = 1; i < k; i++) { int a, b; scanf("%d%d", &a, &b); v[a][b] = true; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { L[i] += !v[i][j]; C[j] += !v[i][j]; if (i == n) { if (C[j] < c[j]) { puts("JIONG!"); return 0; } } } if (L[i] < l[i]) { puts("JIONG!"); return 0; } sum += L[i]; } st = 0, ed = n + m + 1; for (int i = 1; i <= n; i++) { add(st, i, L[i] - l[i]); } for (int i = 1; i <= m; i++) { add(i + n, ed, C[i] - c[i]); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (!v[i][j]) add(i, j + n, 1); } } dinic(); return 0;}