#P9083. 「HNOI2021 省集 Day3」膜拜大丹

    ID: 5167 传统题 2000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-二分图建模最大流最小割定理顶点覆盖补集转化最大权独立集线性 DP懒标记线段树

「HNOI2021 省集 Day3」膜拜大丹

题目描述

丹是万物之神,所以你想去膜拜丹。

现在有两个国家信仰丹,不妨记作国家 A 和国家 B。国家 A 有 nn 座城市,编号为 1∼n1 \sim n;国家 B 有 mm 座城市,编号为 1∼m1 \sim m。

国家 A 和国家 B 之间有单向航线连接,具体地,有长度为 nn 数组 aa 和长度为 mm 的数组 bb,国家 A 的第 ii 座城市有单向航线可以到达国家 B 的编号为 1∼ai1 \sim a_i 的这些城市,国家 B 的第 jj 座城市有单向航线可以到达国家 A 的编号为 1∼bj1 \sim b_j 的这些城市。

所有这 n+mn + m 座城市都无比崇拜丹,定义一次“膜拜”为你选择从某个国家的某座城市出发,沿着单向航线走,不重复地经过至少一座城市,最后回到起点的过程(简单来说就是走一个简单有向环)。为了展现你的虔诚,你希望在你的所有“膜拜”中经过国家 A 的第 ii 座城市不超过 cic_i 次,经过国家 B 的第 jj 座城市不超过 djd_j 次(注意:在一次“膜拜”中起点和终点相同,但是认为起点只经过了一次)。

现在你想知道你可以最多进行多少次“膜拜”。

输入格式

从文件 worship.in 中读入数据。

输入第一行两个整数 n,mn, m 表示两个国家的城市数量。

接下来一行 nn 个整数描述数组 aa。

接下来一行 mm 个整数描述数组 bb。

接下来一行 nn 个整数描述数组 cc。

接下来一行 mm 个整数描述数组 dd。

输出格式

输出到文件 worship.out 中。

输出仅一个整数表示你可以进行的最多的膜拜次数。

样例

样例 1

3 3
3 1 2
1 2 3
1 1 1
1 1 1
1

用符号 AiA_i 表示国家 A 的第 ii 座城市,BjB_j 表示国家 B 的第 jj 座城市,这个样例中所有城市只能经过最多一次,不难发现最好情况下最多只能“膜拜”一次,一种“膜拜”方案为 $A_3 \to B_2 \to A_2 \to B_1 \to A_1 \to B_3 \to A_3$,经过所有点各一次。

样例 2

2 1
1 1
2
1 1
2
2

用符号 AiA_i 表示国家 A 的第 ii 座城市,BjB_j 表示国家 B 的第 jj 座城市,这个样例中 A1,A2A_1, A_2 只能经过最多一次,B1B_1 只能经过最多两次,不难发现最好情况下最多只能“膜拜”两次,一种“膜拜”方案为 A1→B1→A1,A2→B1→A2A_1 \to B_1 \to A_1, A_2 \to B_1 \to A_2,经过 A1,A2A_1, A_2 各一次,经过 B1B_1 两次。

样例 3

见选手目录下的 worship/worship3.in 与 worship/worship3.ans。

该样例满足测试点 4∼64 \sim 6 的性质。

数据范围

对于所有测试数据,满足 1≤n,m≤5×1051\le n,m\le 5\times 10^5,0≤ai≤m0\le a_i\le m,0≤bj≤n0\le b_j\le n,1≤ci,dj≤1091\le c_i,d_j\le 10^9。

每个测试点的具体限制见下表:

测试点编号 nn mm 特殊性质
1∼31\sim 3 ≤10\le 10 A\text{A}
4∼64\sim 6 ≤300\le 300
7∼107\sim 10 ≤5000\le 5000 ≤5000\le 5000 无
11∼1311\sim 13 ≤5×105\le 5\times 10^5
14∼1514\sim 15 ≤5×105\le 5\times 10^5 B\text{B}
16∼2016\sim 20 无

特殊限制 A\text{A}:保证 ∀i∈[1,n],ci=1\forall i\in [1,n],c_i=1 并且 ∀j∈[1,m],dj=1\forall j \in [1,m],d_j=1。

特殊限制 B\text{B}:保证 a1≤a2≤…≤ana_1\le a_2\le \ldots \le a_n。