QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 512 MB Total points: 100
[+11]
Statistics

给定 n,m,k,和两个正整数序列 a1...n,b1...m,以及一个 k×k01 矩阵 s1...k,1...k

考虑一张有向图 G=(V,E),其中 V={S,T}({0,1}×([1,k]Z)2),而 E=E1E2E3 由三部分组成:

  • E1={(S,(0,1,ai))1in}{((1,k,bi),T)1im}
  • E2={((1,i,j),(0,i+1,j))1i<k,1jk}{(1,i,j),(0,i,j+1))1ik,1j<k}
  • E3={((0,i,j),(1,i,j))1i,jk,si,j=1}

简单来说,你可以看成每个格子 (i,j),1i,jk 被拆成了一个入点 (0,i,j) 和一个出点 (1,i,j)E1 描述了 S,T 与这些点之间的边,由 a,b 决定;E2 描述了每个格子的出点连向它上方和右方格子的入点的边;E3 描述了每个格子的入点连向出点的边,由 s 决定。

现在我们将 G 看成一个网络,每条边的容量是 1。你需要求出以 S 为源点,以 T 为汇点的最大流,以及最大流的数量(两个流被认为是不同的,当且仅当存在一条边在两个流中的流量不同)。

输入格式

第一行三个正整数 n,m,k

第二行 n 个正整数 1a1<a2<...<ank

第三行 m 个正整数 1b1<b2<...<bmk

接下来 k 行,每行一个长度为 k 的 01 字符串,表示矩阵 s

输出格式

输出一行两个非负整数,分别表示最大流和最大流的数量,后者对 109+7 取模。

数据范围与约定

对于全部数据,1n,mk400

子任务编号nk特殊性质子任务分值
1775
218185
31040010
410040025
5400400n=m 且最大流为 n10
6400400最大流为 n25
740040020