QOJ.ac

QOJ

Time Limit: 2.5 s Memory Limit: 512 MB Total points: 100

# 7648. 网格图最大流计数

统计

给定 $ n,m,k $,和两个正整数序列 $ a_{1...n},b_{1...m} $,以及一个 $ k\times k $ 的 $ 01 $ 矩阵 $ s_{1...k,1...k} $。

考虑一张有向图 $ G=(V,E) $,其中 $ V=\{S,T\}\cup(\{0,1\}\times ([1,k]\cap\mathbb{Z})^2) $,而 $ E=E_1\cup E_2\cup E_3 $ 由三部分组成:

  • $ E_1=\{(S,(0,1,a_i)) \mid 1\le i\le n\}\cup\{((1,k,b_i),T)\mid 1\le i\le m\} $
  • $ E_2=\{((1,i,j),(0,i+1,j))\mid1\le i<k,1\le j\le k\}\cup \{(1,i,j),(0,i,j+1))\mid1\le i\le k,1\le j<k\} $
  • $ E_3=\{((0,i,j),(1,i,j))\mid 1\le i,j\le k,s_{i,j}=1\} $

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

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

输入格式

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

第二行 $ n $ 个正整数 $ 1\le a_1<a_2<...<a_n\le k $。

第三行 $ m $ 个正整数 $ 1\le b_1<b_2<...<b_m\le k $。

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

输出格式

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

数据范围与约定

对于全部数据,$ 1\le n,m\le k\le400 $。

子任务编号$ n\le $$ k\le $特殊性质子任务分值
$ 1 $$ 7 $$ 7 $$ 5 $
$ 2 $$ 18 $$ 18 $$ 5 $
$ 3 $$ 10 $$ 400 $$ 10 $
$ 4 $$ 100 $$ 400 $$ 25 $
$ 5 $$ 400 $$ 400 $$ n=m $ 且最大流为 $ n $$ 10 $
$ 6 $$ 400 $$ 400 $最大流为 $ n $$ 25 $
$ 7 $$ 400 $$ 400 $$ 20 $