给定一个 n×n 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 (x,y),(u,v) 能互相攻击当前仅当满足以下两个条件： 1. x=u 或 y=v 2.对于 (x,y) 与 (u,v) 之间的所有位置，均不是障碍。 现在有 q 个询问，每个询问给定 ki，要求从棋盘中选出 ki 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？ n≤50 , q≤10000 , k≤棋盘中空位置数量 本来是道费用流大裸题，结果只有我没想出来。考虑棋盘模型，一排表示行，一排表示列，然后棋子相互攻击的贡献是递增的，所以 S 到表示行的点和 表示列的点到 T 之间连递增费用的边，如果一个位置不是障碍，就把对应行列连起来，障碍隔开的行和列只要建不同的点即可。
#include<bits/stdc++.h> const int N = 55; const int P = N * N * 2; const int INF = 1e9; template <typename T> void read(T &x) { x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()); for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; } int n, a[N][N], b[N][N], first[P], s, q[P + 10], dis[P], from[P], ans[N * N], cnt, line, S, T, Q, x; bool inq[P]; char ch[N][N]; struct edge{ int x, y, f, v, next; }mp[N*N*N*N*2]; void ins(int x, int y, int f, int v) { //printf("ins x=%d y=%d f=%d v=%d\n", x, y, f, v); mp[++s] = (edge) {x, y, f, v, first[x]}; first[x] = s; mp[++s] = (edge) {y, x, 0, -v, first[y]}; first[y] = s; } bool SPFA() { for (int i=S; i <= T; i++) inq[i] = 0, dis[i] = INF; int head = 1, tail = 2; inq[q[head] = S] = 1; dis[q[head]] = 0; while (head != tail) { int x = q[head]; //printf("x=%d\n", x); for (int t=first[x]; t; t=mp[t].next) { //printf("walk x=%d y=%d f=%d v=%d\n", mp[t].x, mp[t].y, mp[t].f, mp[t].v); if (mp[t].f && dis[x] + mp[t].v < dis[mp[t].y]) { dis[mp[t].y] = dis[x] + mp[t].v; from[mp[t].y] = t; if (!inq[mp[t].y]) { inq[q[tail++] = mp[t].y] = 1; if (tail > P) tail = 1; } } } inq[q[head++]] = 0; if (head > P) head = 1; } return dis[T] < INF; } void mcf(int i) { int fl = INF; for (int x=T; x != S; x=mp[from[x]].x) fl = std::min(fl, mp[from[x]].f); for (int x=T; x != S; x=mp[from[x]].x) mp[from[x]].f -= fl, mp[from[x]^1].f += fl; ans[i] = ans[i - 1] + dis[T]; //printf("i=%d Dinic=%d\n", i, dis[T]); } int main() { //freopen("A.in", "r", stdin); //freopen("A.out", "w", stdout); read(n); for (int i=1; i <= n; i++) scanf("%s", ch[i] + 1); for (int i=0; i <= n + 1; i++) ch[0][i] = ch[n + 1][i] = ch[i][0] = ch[i][n + 1] = '#'; for (int i=1; i <= n; i++) for (int j=1; j <= n; j++) { if (ch[i][j] == '#') continue; if (ch[i][j - 1] == '.') a[i][j] = a[i][j - 1]; else a[i][j] = ++cnt; } line = cnt; for (int j=1; j <= n; j++) for (int i=1; i <= n; i++) { if (ch[i][j] == '#') continue; if (ch[i - 1][j] == '.') b[i][j] = b[i - 1][j]; else b[i][j] = ++cnt; } S = 0; T = cnt + 1; s = 1; for (int j=1; j <= n; j++) for (int i=1; i <= n; i++) if (ch[i][j] == '.') ins(a[i][j], b[i][j], 1, 0); for (int i=1; i <= line; i++) for (int j=0; j < n; j++) ins(S, i, 1, j); for (int i=line + 1; i <= cnt; i++) for (int j=0; j < n; j++) ins(i, T, 1, j); for (int i=1; SPFA(); i++) mcf(i); for (read(Q); Q--;) read(x), printf("%d\n", ans[x]); return 0; }