首页 > 其他分享 >【YBT2023寒假Day11 B】催眠大师(费用流)

【YBT2023寒假Day11 B】催眠大师(费用流)

时间:2023-02-21 19:46:28浏览次数:55  
标签:val int YBT2023 KK 寒假 Day11 go now dis

催眠大师

题目链接:YBT2023寒假Day11 B

题目大意

有一个 n*n 的棋盘,有一些位置有障碍。
然后定义棋盘上两个位置能相互攻击当且仅当在同一行或同一列,且之间的所有位置都没有障碍。
多次询问每次给你 k 求在棋盘中选 k 个没有障碍的位置放棋子,最小能互相攻击的对数。

思路

你可以发现障碍把每一行和每一列分别都拆成了若干个段,里面的点就互相可以攻击。
那就是这些段每个的个数 \(d\) 的 \(\binom{d}{2}\) 之和。

看到 \(n\) 很小,但是如果我们直接 \(O(n^2)\) 网络流也不行。
但是因为是棋盘,一个经典的方法就是行列分别建点,然后之间的边标记图中的点。
不过你注意到一行或者一列个数的不是线性的。

不过我们思考网络流每次跑费用最小的地方,那在能互相攻击到的位置上,你每选一个点,增加的费用是每次递增,增加 \(1\) 的。
那我们可以改成建两排点分别是行里面互相能到的点和列里面互相能到的点。
然后原本行列连边就改成在它属于的互相能到的点连边。

然后每个行列互相能到的点到分别源点汇点就连多条边,每条的流量是 \(1\),费用是递增的 \(1\sim x\)。
然后跑费用流就好了。

代码

#include<queue>
#include<cstdio>
#include<iostream>
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const int N = 55;
int n, a[N][N], ans[N * N], coll[N][N], colr[N][N], sz[N * N * 2];
int S, T, le[N * N * 2], KK, tot, Tot;
struct node {
	int x, val, to, nxt, op;
}e[N * N * N * N];
char c;

int deg[N * N * 2], dis[N * N * 2], lee[N * N * 2];
bool in[N * N * 2];
queue <int> Q;

void add(int x, int y, int z, int val) {
	e[++KK] = (node){z, val, y, le[x], KK + 1}; le[x] = KK;
	e[++KK] = (node){0, -val, x, le[y], KK - 1}; le[y] = KK;
}

bool SPFA() {
	while (!Q.empty()) Q.pop();
	for (int i = 0; i <= tot; i++) deg[i] = 0, dis[i] = INF, lee[i] = le[i];
	Q.push(S); deg[S] = 1; dis[S] = 0; in[S] = 1;
	while (!Q.empty()) {
		int now = Q.front(); Q.pop();
		for (int i = le[now]; i; i = e[i].nxt)
			if (dis[e[i].to] > dis[now] + e[i].val && e[i].x) {
				dis[e[i].to] = dis[now] + e[i].val;
				deg[e[i].to] = deg[now] + 1;
				if (!in[e[i].to]) {
					in[e[i].to] = 1; Q.push(e[i].to);
				}
			}
		in[now] = 0;
	}
	return dis[T] != dis[0];
}

int dfs(int now, int sum) {
	if (now == T) return sum;
	int go = 0;
	for (int &i = lee[now]; i; i = e[i].nxt)
		if (dis[e[i].to] == dis[now] + e[i].val && deg[e[i].to] == deg[now] + 1 && e[i].x) {
			int this_go = dfs(e[i].to, min(sum - go, e[i].x));
			if (this_go) {
				e[i].x -= this_go;
				e[e[i].op].x += this_go;
				go += this_go; if (go == sum) return go;
			}
		}
	deg[now] = -1;
	return go;
}

int main() {
	freopen("table.in", "r", stdin);
	freopen("table.out", "w", stdout);
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			c = getchar(); while (c != '.' && c != '#') c = getchar();
			if (c == '.') a[i][j] = 1;
				else a[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (!a[i][j]) continue;
			if (!a[i - 1][j]) coll[i][j] = ++Tot;
				else coll[i][j] = coll[i - 1][j];
			sz[coll[i][j]]++;
			if (!a[i][j - 1]) colr[i][j] = ++Tot;
				else colr[i][j] = colr[i][j - 1];
			sz[colr[i][j]]++;
		}
	
	S = Tot + 1; T = S + 1; tot = T;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			if (!a[i][j]) continue;
			add(coll[i][j], colr[i][j], 1, 0);
			if (coll[i][j] != coll[i - 1][j])
				for (int k = 1; k <= sz[coll[i][j]]; k++) add(S, coll[i][j], 1, k - 1);
			if (colr[i][j] != colr[i][j - 1])
				for (int k = 1; k <= sz[colr[i][j]]; k++) add(colr[i][j], T, 1, k - 1);
		}
	
	int num = 0;
	while (SPFA()) {
		int x = dfs(S, INF);
		for (int i = 1; i <= x; i++) num++, ans[num] = ans[num - 1] + dis[T];
	}
	
	int q; scanf("%d", &q);
	while (q--) {
		int x; scanf("%d", &x); printf("%d\n", ans[x]);
	}
	
	return 0;
}

标签:val,int,YBT2023,KK,寒假,Day11,go,now,dis
From: https://www.cnblogs.com/Sakura-TJH/p/YBT2023Day11_B.html

相关文章

  • day11 事件相关笔记
    day11事件上事件的概述事件是指代一个东西的操作被另外一个东西监听以后的一个过程(事件),这个过程可以完成对应的操作(处理函数)事件监听器是一个标准的观察者模式(observer)......
  • day11
    运算符PS.byte,short,char用运算符运算后自动转型为int类型......
  • 【YBT2023寒假Day11 A】海妖沙龙(计算几何)
    海妖沙龙题目链接:YBT2023寒假Day11A题目大意平面上有n个点,然后对于一个排列,如果按顺序走对于的点,会形成若干个线段组成的路径,然后你从前一个线段走到下一个线段端点......
  • H - 线段树 1【GDUT_22级寒假训练专题五】
    H-线段树1原题链接题意区间修改区间查询线段树简介线段树是一颗二叉树,他能通过树的分支将一块区间划分为数个单元区间,每个单元区间对应线段树中的一个叶结点。如......
  • 【YBT2023寒假Day10 C】娄居吉勾(点分树)
    娄居吉勾题目链接:YBT2023寒假Day10C题目大意有一个n个点m条边的无向连通图,每个点至多在k个简单环上。然后有q个操作,标记一个没有标记过的点,或者给你一个点求......
  • 寒假训练第四周
      题目大意意思就是给一个n和一个kk是2的k次方n是分子在2的k次方上面从1到n分子依次加一然后要进行分数有理化然后把有理化的分子相加即可思路因为是2的k次方......
  • 寒假学习记录(三)
    这个作业属于哪个课程<班级的链接>这个作业要求在哪里<作业要求的链接>这个作业的目标学有所得一、写在前面对于每次寒假作业的目标,我给自己设定的都......
  • 【YBT2023寒假Day10 B】随机游走(记忆化搜索)
    随机游走题目链接:YBT2023寒假Day10B题目大意有n个点排成环,你一开始在1号点,每次可以等概率选择左边跳两格,左边跳一格,右边跳一格,右边跳两格。走到一个走过的点就停......
  • 【YBT2023寒假Day10 A】集合比较(数学)(启发式分裂)
    集合比较题目链接:YBT2023寒假Day10A题目大意给你一个长度为n的排列p,定义两个大小为n不可重集合的比较方式是先比较各自第p1小的元素,如果相同比p2,以此类推。给......
  • 寒假学习总结
    这个作业属于哪个课程班级这个作业要求在哪里作业的要求这个作业的目标对寒假学习的总结寒假学习总结一、回顾在本次寒假的学习当中,收益颇丰,每次作业......