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..#.####..#...#.17
样例输出
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#define ll long long#define N 55using 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="< <<" to="< <<" flow="< <<" cost="< <<"\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 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 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