Loj 6068. 「2017 山东一轮集训 Day4」棋盘
题目描述
给定一个 $ n \times n $ 的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置 $ (x, y),(u, v) $ 能互相攻击当前仅当满足以下两个条件：
- $ x = u $ 或 $ y = v $
- 对于 $ (x, y) $ 与 $ (u, v) $ 之间的所有位置，均不是障碍。
现在有 $ q $ 个询问，每个询问给定 $ k_i $，要求从棋盘中选出 $ k_i $ 个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
输入格式
第一行一个整数 $ n $。
接下来输入一个 $ n \times n $ 的字符矩阵，一个位置若为 .，则表示这是一个空位置，若为 #，则为障碍。
第 $ n + 2 $ 行输入一个整数 $ q $ 代表询问个数。
接下来 $ q $ 行，每行一个整数 $ k $，代表要放的棋子个数。
样例
样例输入
4
..#.
####
..#.
..#.
1
7
样例输出
2
数据范围与提示
对于 $ 20% $ 的数据，$ n \leq 5 $；
对于 $ 40% $ 的数据，$ n \leq 10 $；
另外有 $ 20% $ 的数据，$ q = 1 $；
对于 $ 100% $ 的数据，$ n \leq 50; q \leq 10000; k \leq $ 棋盘中空位置数量。
感觉对这种棋盘类的题不太熟啊！
这种棋盘上填棋子的题大概率是网络流之类的东西。
棋盘建图的一般套路就是：将每个行连通块和列连通块拿出来，分别于源点和汇点连边，对于每个\((x,y)\)，有该点所在的行连通块向列连通块连边，流量为\(1\)，表示这个位置可以放一个棋子。
然后这道题同一行/列可以放多个棋子，于是源点到某一个连通块连多条边。边权为差分值\(\frac{i\cdot(i+1)}{2}-\frac{i\cdot (i-1)}{2}=i\)。然后发现他的增量是单调递增的，所以直接费用流不会出问题。汇点同理。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 55
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
int n;
char mp[N][N];
int S,T;
struct road {
int to,next;
int flow,c;
}s[1200010];
int h[N*N],cnt=1;
void add(int i,int j,int f,int c) {
// cout<<"fr="<<i<<" to="<<j<<" flow="<<f<<" cost="<<c<<"\n";
s[++cnt]=(road) {j,h[i],f,c};h[i]=cnt;
s[++cnt]=(road) {i,h[j],0,-c};h[j]=cnt;
}
int tot;
int hbel[N][N],lbel[N][N];
int res;
bool vis[N*N];
queue<int>q;
int dis[N*N];
int ans[N*N],now;
int fr[N*N],e[N*N];
bool in[N*N];
int mx;
bool spfa() {
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
q.push(S);
while(!q.empty()) {
int v=q.front();q.pop();
in[v]=0;
for(int i=h[v];i;i=s[i].next) {
int to=s[i].to;
if(s[i].flow&&dis[to]>dis[v]+s[i].c) {
dis[to]=dis[v]+s[i].c;
fr[to]=v;
e[to]=i;
if(!in[to]) in[to]=1,q.push(to);
}
}
}
if(dis[T]>1e9) return 0;
for(int i=T;i;i=fr[i]) {
s[e[i]].flow--;
s[e[i]^1].flow++;
}
now++;
ans[now]=ans[now-1]+dis[T];
if(now==mx) return 0;
return 1;
}
vector<int>que;
int size[N*N];
int main() {
n=Get();
for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(mp[i][j]=='#') continue ;
res++;
if(mp[i][j-1]!='.') hbel[i][j]=++tot;
else hbel[i][j]=hbel[i][j-1];
}
}
for(int j=1;j<=n;j++) {
for(int i=1;i<=n;i++) {
if(mp[i][j]=='#') continue ;
if(mp[i-1][j]!='.') lbel[i][j]=++tot;
else lbel[i][j]=lbel[i-1][j];
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
size[hbel[i][j]]++,size[lbel[i][j]]++;
S=0,T=tot+1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(mp[i][j]!='.') continue ;
if(hbel[i][j]!=hbel[i][j-1]) {
for(int q=1;q<=size[hbel[i][j]];q++) add(S,hbel[i][j],1,q-1);
}
if(lbel[i][j]!=lbel[i-1][j]) {
for(int q=1;q<=size[lbel[i][j]];q++) add(lbel[i][j],T,1,q-1);
}
add(hbel[i][j],lbel[i][j],1,0);
}
}
int Q=Get();
for(int i=0;i<Q;i++) {
int a=Get();
mx=max(mx,a);
que.push_back(a);
}
while(spfa());
for(int i=0;i<Q;i++) cout<<ans[que[i]]<<"\n";
return 0;
}