首页 > 代码库 > 【bzoj4930】棋盘 费用流
【bzoj4930】棋盘 费用流
题目描述
给定一个n×n的棋盘，棋盘上每个位置要么为空要么为障碍。定义棋盘上两个位置(x,y),(u,v)能互相攻击当前仅
当满足以下两个条件：
1:x=u或y=v
2:对于(x,y)与(u,v)之间的所有位置，均不是障碍。
现在有q个询问，每个询问给定ki，要求从棋盘中选出ki个空位置来放棋子，问最少互相能攻击到的棋子对数是多少？
输入
第一行一个整数n。
接下来输入一个n×n的字符矩阵，一个位置若为.，则表示这是一个空位置，若为#，则为障碍。
第n+2行输入一个整数q代表询问个数。
接下来q行，每行一个整数k，代表要放的棋子个数。
n ≤ 50, q ≤ 10000, k ≤ 棋盘中空位置数量
输出
输出共q行，每行代表对应询问的最少的互相能攻击到的棋子对数。
样例输入
4
..#.
####
..#.
..#.
1
7
样例输出
2
题解
费用流， bzoj4554 的强化版
按照那道题的思路，把相互影响的行和列的部分拿出来，同一个点的行部分和列部分之间连边。
不过这道题是固定棋子数，问最小的影响的棋子对数。
考虑，一个行或列的部分，如果存在k个棋子，那么相互影响的棋子对数为$\frac{k(k-1)}2$对（两个棋子之间隔着其它棋子也算相互影响）。
所以我们可以使用拆边法来解决，从S到行的部分、从列的部分到T连d条边，其中d为该部分的位置数。第i条边的费用为$\frac{i(i-1)}2-\frac{(i-1)(i-2)}2=i-1$。
然后跑费用流。在此过程中，由于每条增广路的容量必定为1，所以相当于每次多放置了一个棋子。这样我们可以只跑一次EK费用流即可预处理出所有答案，然后再$O(1)$回答。
时间有点长但可以过，可以动态加边来提高效率（这里懒了没有写）
#include <cstdio>#include <cstring>#include <queue>#define N 6010#define M 1200010#define inf 0x3f3f3f3fusing namespace std;queue<int> q;int map[60][60] , bx[60][60] , tx , by[60][60] , ty , sx[N] , sy[N] , head[N] , to[M] , val[M] , cost[M] , next[M] , cnt = 1 , s , t , dis[N] , from[N] , pre[N] , ans[N];char str[60];void add(int x , int y , int v , int c){ to[++cnt] = y , val[cnt] = v , cost[cnt] = c , next[cnt] = head[x] , head[x] = cnt; to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , next[cnt] = head[y] , head[y] = cnt;}bool spfa(){ int x , i; memset(from , -1 , sizeof(from)); memset(dis, 0x3f , sizeof(dis)); dis[s] = 0 , q.push(s); while(!q.empty()) { x = q.front() , q.pop(); for(i = head[x] ; i ; i = next[i]) if(val[i] && dis[to[i]] > dis[x] + cost[i]) dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]); } return ~from[t];}void mincost(){ int k = 0 , i; while(spfa()) { k ++ , ans[k] = ans[k - 1] + dis[t]; for(i = t ; i != s ; i = from[i]) val[pre[i]] -- , val[pre[i] ^ 1] ++ ; }}int main(){ int n , q , i , j , x; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) { scanf("%s" , str + 1); for(j = 1 ; j <= n ; j ++ ) map[i][j] = (str[j] == ‘#‘); } for(i = 1 ; i <= n ; i ++ ) { tx ++ ; for(j = 1 ; j <= n ; j ++ ) bx[i][j] = tx , sx[tx] ++ , tx += map[i][j]; } for(j = 1 ; j <= n ; j ++ ) { ty ++ ; for(i = 1 ; i <= n ; i ++ ) by[i][j] = ty , sy[ty] ++ , ty += map[i][j]; } s = 0 , t = tx + ty + 1; for(i = 1 ; i <= tx ; i ++ ) for(j = 0 ; j < sx[i] ; j ++ ) add(s , i , 1 , j); for(i = 1 ; i <= ty ; i ++ ) for(j = 0 ; j < sy[i] ; j ++ ) add(i + tx , t , 1 , j); for(i = 1 ; i <= n ; i ++ ) for(j = 1 ; j <= n ; j ++ ) if(!map[i][j]) add(bx[i][j] , by[i][j] + tx , 1 , 0); mincost(); scanf("%d" , &q); while(q -- ) scanf("%d" , &x) , printf("%d\n" , ans[x]); return 0;}
【bzoj4930】棋盘 费用流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。