题目大意
给定一个
n
×
m
n\times m
n×m 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置
(
x
,
y
)
,
(
u
,
v
)
(x,y),(u,v)
(x,y),(u,v)能互相攻击当前仅当满足以下两个条件：
1.
x
=
u
x=u
x=u或
y
=
v
y=v
y=v
2.对于
(
x
,
y
)
(x,y)
(x,y)与
(
u
,
v
)
(u,v)
(u,v)之间的所有位置，均不是障碍。
现在有
q
q
q个询问，每个询问给定
m
m
m，要求从棋盘中选出
m
m
m个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
思路：
考虑费用流。对于每一行和每一列，连续没有障碍的格子组成一个连续段。如果当前位置为
(
i
,
j
)
(i,j)
(i,j)且不是障碍，则该横连续段向该列连续段连一条容量为1的边，费用为0。代表这里放不会有贡献。
然后源点向所有横连续段建边，边的容量为连续段的大小x，费用为
(
x
2
)
\binom{x}{2}
(2x)。
然后汇点同理。
但显然这样是不行的，因为一个连续段放的棋子个数是不确定的。所以分开建边，建x条边，第i条容量为1，费用为i-1，这样就可以满足
(
x
2
)
\binom{x}{2}
(2x)的条件。
然后每次增加1流量，跑费用流。
c
o
d
e
code
code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 100;
int n, m, m2, S, T;
int a[MAXN][MAXN], r[MAXN][MAXN], c[MAXN][MAXN], d[MAXN * MAXN];
int ans[MAXN * MAXN];
int head[MAXN * MAXN], crn[MAXN * MAXN], tot = 1, last[MAXN * MAXN];
int dis[MAXN * MAXN];
struct node {
int to, next, w, dis;
}b[MAXN * MAXN * 2];
bool v[MAXN * MAXN];
void add(int x,int y,int w,int dis) {
b[++ tot] = (node) {y, head[x], w, dis};
head[x] = tot;
}
bool spfa() {
memset(v, 0, sizeof(v));
memset(dis, 0x3f3f3f3f3f, sizeof(dis));
dis[S] = 0;
queue<int> q;
q.push(S);
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i = head[x]; i; i = b[i].next) {
int y = b[i].to;
if(b[i].w > 0 && dis[y] > dis[x] + b[i].dis) {
dis[y] = dis[x] + b[i].dis;
crn[y] = x;
last[y] = i;
if(!v[y]) v[y] = 1, q.push(y);
}
}
v[x] = 0;
}
// cout<<dis[T]<<endl;
return dis[T] != 1061109567;
}
void dinic() {
int x = 1;
while(spfa()) {
ans[x] = ans[x - 1] + dis[T];
// cout<<ans[x]<<endl;
for(int i = T; i != S; i = crn[i]) {
b[last[i]].w --;
b[last[i] ^ 1].w ++;
}
x ++;
if(x > n * n) return ;
}
}
int main() {
freopen("table.in", "r", stdin);
freopen("table.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
string s;
cin>>s;
for(int j = 0; j < s.size(); j ++)
if(s[j] == '.') a[i][j + 1] = 1;
else a[i][j + 1] = -1;
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
if(a[i][j] == -1) continue;
if(a[i][j - 1] != 1) r[i][j] = ++ m;
else r[i][j] = r[i][j - 1];
}
}
for(int j = 1; j <= n; j ++) {
for(int i = 1; i <= n; i ++) {
if(a[i][j] == -1) continue;
if(a[i - 1][j] != 1) c[i][j] = ++ m2;
else c[i][j] = c[i - 1][j];
}
}
S = 0, T = m + m2 + 1;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++) {
if(a[i][j] == -1) continue;
add(r[i][j], c[i][j] + m, 1, 0);
add(c[i][j] + m, r[i][j], 0, 0);
d[r[i][j]] ++, d[c[i][j] + m] ++;
}
for(int i = 1; i <= m; i ++)
for(int j = 1; j <= d[i]; j ++)
add(S, i, 1, j - 1), add(i, S, 0, j - 1);
for(int i = m + 1; i <= m + m2; i ++)
for(int j = 1; j <= d[i]; j ++)
add(i, T, 1, j - 1), add(T, i, 0, j - 1);
dinic();
int q;
scanf("%d", &q);
while(q --) {
int x;
scanf("%d", &x);
printf("%d\n", ans[x]);
}
return 0;
}
