#P11168. 「CMOI R1」First Town of This Journey/Grid Covering

    ID: 10358 Type: RemoteJudge 100ms 128MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>数学2024洛谷原创O2优化

「CMOI R1」First Town of This Journey/Grid Covering

题目背景

Link:First Town of This Journey$\small\color{white}/10^{\text{th}}\text{Problem by AtC}.$

本题中认为两个点间的连线为以这两个点作为端点的线段。

题目描述

BiOI\text{BiOI} 有一个 nnmm 列的网格。你需要选出最少的格点,使得任意两个不同的格点的连线至少经过一个被选中的点(这里我们认为一条线段经过了它的两个端点)。

CmOI\text{CmOI} 觉得这个问题太简单了,所以他会另外给定 a,b,xa,b,x,表示第 aa 行第 bb 列的格点必须被或不被选中:

  • x=0x=0 时该格点不可选中;
  • x=1x=1 时该格点必须选中。

你只需要求出最少选出几个格点,BiOI\text{BiOI}CmOI\text{CmOI} 会把网格和你的答案一起丢给 ArCu\text{ArCu} 让他构造方案。

输入格式

第一行两个整数 n,mn,m

第二行三个整数 a,b,xa,b,x

输出格式

一行一个整数,最少选出的格点数。

3 3
2 2 1
5
2 5
1 3 0
7
4 5
3 2 0
16

提示

Details about Subtasks:\text{Details about Subtasks}:

所有数据满足 $1\leq n,m<2^{32},1\leq a\leq n,1\leq b\leq m,0\leq x\leq 1$。

  • Subtask 1:1n,m10,5 points.\text{Subtask 1}:1\leq n,m\leq 10,\text{5 points.}
  • Subtask 2:x=0,25 points.\text{Subtask 2}:x=0,\text{25 points}.
  • Subtask 3:x=1,30 points.\text{Subtask 3}:x=1,\text{30 points.}
  • Subtask 4:40 points.\text{Subtask 4}:\text{40 points.}

Sample Explanation:\text{Sample Explanation}:

  • Sample 1:\text{Sample 1}:

此时网格有 3333 列,要求第 22 行第 22 列的格点必须被选中。

最优方案如下(黑色是被选中的格点):

010111010

注意以下方案并不合法:

  • 图中给出了两种方法使得两个不同的格点间连线不经过黑点;
  • 第二行第二列的格点没有被选中,输入中要求这个格点必须被选中。

011100011

以及我们认为端点在黑点上算是经过黑点。也就是说下面的这种连线经过了一个黑色格点。

011110011