给定一个 n * n 的棋盘，棋盘上每个位置要么为空要么为障碍。定义
棋盘上两个位置 (x，y)和(u， v) 能互相攻击当前仅当满足以下两个条件：
• x = u 或 y = v
• 对于 (x; y) 与 (u; v) 之间的所有位置，均不是障碍。
现在有 q 个询问，每个询问给定 ki，要求从棋盘中选出 ki 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
输入格式
第一行一个整数 n。
接下来输入一个 n * n 的字符矩阵，一个位置若为.，则表示这是一个
空位置，若为 #，则为障碍。
第 n + 2 行输入一个整数 q 代表询问个数。
接下来 q 行，每行一个整数 k，代表要放的棋子个数。
输出格式
输出共 q 行，每行代表对应询问的最少的互相能攻击到的棋子对数。
样例数据一
chess.in
4 2
. . # .
# # # #
. . # .
. . # .
1
7
chess.out
2
分析：
这道题采用了缩点的思路：把每一个非障碍点相连的横向点缩成一个点，相连的纵向点缩成一个点，
在网络流建图中，横向点作为x部，纵向点作为y部，
每一个横向点向与ta有交集的横向点连一条流量是1，费用是0的边，
每一个横向点包含几（n）个点，就从源点向其连多少（n）条流量是1，费用分别是（0,1,2,3…n）,
对于每个纵向点也如此处理（只不过是向汇点连边），
之后跑一个最小费用最大流，记录每次增广的费用（ans[i]）,这样在询问时直接输出就好了
看图理解一下：
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int INF=0x33333333;
int n,q;
int map1[55][55],map2[55][55],maxx=0;
struct node{
int x,y,nxt,v,c;
};
node way[250010];
int st[250000],tot=-1,s,t,pre[30000],p[30000],d[30000],ans[30000];
void add(int u,int w,int z,int co)
{
tot++; way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];way[tot].c=co;st[u]=tot;
tot++;way[tot].x=w;way[tot].y=u;way[tot].v=0;way[tot].nxt=st[w];st[w]=tot;way[tot].c=-co;
}
void lianbian()
{
s=0; t=29999;
int i,j,k,blo=0;
int tt=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (map1[i][j]==0)
{
blo=0;
tt++;
int f1=j;
while (f1<=n&&map1[i][f1]==0)
{
map1[i][f1]=tt;
add(s,tt,1,blo);
blo++;
f1++;
}
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (map2[i][j]==0)
{
blo=0;
tt++;
int f1=i;
while (f1<=n&&map2[f1][j]==0)
{
map2[f1][j]=tt;
add(map1[f1][j],tt,1,0);
add(tt,t,1,blo);
blo++;
f1++;
}
}
return;
}
int spfa()
{
int i;
memset(pre,0,sizeof(pre));
memset(p,1,sizeof(p));
memset(d,0x33,sizeof(d)); //花费
queue<int> q;
q.push(s);
d[s]=0;
p[s]=0;
while (!q.empty())
{
int r=q.front();
q.pop();
for (i=st[r];i!=-1;i=way[i].nxt)
{
if (way[i].v&&d[way[i].y]>d[r]+way[i].c) //这条路可走而且有修改价值
{
d[way[i].y]=d[r]+way[i].c;
pre[way[i].y]=i; //修改来自哪条边
if (p[way[i].y])
{
p[way[i].y]=0;
q.push(way[i].y);
}
}
}
p[r]=1;
}
return d[t]<INF;
}
int doit()
{
int an=0,sum,i,j=0;
while (spfa())
{
sum=INF;
for (i=t;i!=s;i=way[pre[i]].x) //从汇点检索一下是通过哪条最小费用增广路
sum=min(sum,way[pre[i]].v); //pre：以i为终点的边的编号
an+=d[t]*sum;
for (i=t;i!=s;i=way[pre[i]].x)
{
way[pre[i]].v-=sum;
way[pre[i]^1].v+=sum;
}
ans[++j]=an;
}
}
int main()
{
//freopen("chess.in","r",stdin);
//freopen("chess.out","w",stdout);
memset(st,-1,sizeof(st));
scanf("%d",&n);
for (int i=1;i<=n;i++)
{
char mm[55];
scanf("%s",&mm);
for (int j=0;j<n;j++)
if (mm[j]=='#') map1[i][j+1]=map2[i][j+1]=-1;
}
lianbian();
doit();
scanf("%d",&q);
for (int i=1;i<=q;i++)
{
int opt;
scanf("%d",&opt);
printf("%d
",ans[opt]);
}
return 0;
}