#P11168. 「CMOI R1」First Town of This Journey/Grid Covering
「CMOI R1」First Town of This Journey/Grid Covering
题目背景
$\small\color{white}/10^{\text{th}}\text{Problem by AtC}.$
本题中认为两个点间的连线为以这两个点作为端点的线段。
题目描述
有一个 行 列的网格。你需要选出最少的格点,使得任意两个不同的格点的连线至少经过一个被选中的点(这里我们认为一条线段经过了它的两个端点)。
觉得这个问题太简单了,所以他会另外给定 ,表示第 行第 列的格点必须被或不被选中:
- 时该格点不可选中;
- 时该格点必须选中。
你只需要求出最少选出几个格点, 和 会把网格和你的答案一起丢给 让他构造方案。
输入格式
第一行两个整数 ;
第二行三个整数 。
输出格式
一行一个整数,最少选出的格点数。
3 3
2 2 1
5
2 5
1 3 0
7
4 5
3 2 0
16
提示
所有数据满足 $1\leq n,m<2^{32},1\leq a\leq n,1\leq b\leq m,0\leq x\leq 1$。
此时网格有 行 列,要求第 行第 列的格点必须被选中。
最优方案如下(黑色是被选中的格点):
注意以下方案并不合法:
- 图中给出了两种方法使得两个不同的格点间连线不经过黑点;
- 第二行第二列的格点没有被选中,输入中要求这个格点必须被选中。
以及我们认为端点在黑点上算是经过黑点。也就是说下面的这种连线经过了一个黑色格点。