#1781. 网格图最大流计数
网格图最大流计数
网格图最大流计数
题目描述
标题: 网格图最大流计数 - Problem - QOJ.ac
给定 n,m,k,和两个正整数序列 a1...n,b1...m,以及一个 k×k 的 01 矩阵 s1...k,1...k。
考虑一张有向图 G=(V,E),其中 V={S,T}∪({0,1}×([1,k]∩Z)2),而 E=E1∪E2∪E3 由三部分组成:
- E1={(S,(0,1,ai))∣1≤i≤n}∪{((1,k,bi),T)∣1≤i≤m}
- E2={((1,i,j),(0,i+1,j))∣1≤i<k,1≤j≤k}∪{(1,i,j),(0,i,j+1))∣1≤i≤k,1≤j<k}
- E3={((0,i,j),(1,i,j))∣1≤i,j≤k,si,j=1}
简单来说,你可以看成每个格子 (i,j),1≤i,j≤k 被拆成了一个入点 (0,i,j) 和一个出点 (1,i,j)。E1 描述了 S,T 与这些点之间的边,由 a,b 决定;E2 描述了每个格子的出点连向它上方和右方格子的入点的边;E3 描述了每个格子的入点连向出点的边,由 s 决定。
现在我们将 G 看成一个网络,每条边的容量是 1。你需要求出以 S 为源点,以 T 为汇点的最大流,以及最大流的数量(两个流被认为是不同的,当且仅当存在一条边在两个流中的流量不同)。
输入格式
第一行三个正整数 n,m,k。
第二行 n 个正整数 1≤a1<a2<...<an≤k。
第三行 m 个正整数 1≤b1<b2<...<bm≤k。
接下来 k 行,每行一个长度为 k 的 01 字符串,表示矩阵 s。
输出格式
输出一行两个非负整数,分别表示最大流和最大流的数量,后者对 109+7 取模。
数据范围与约定
对于全部数据,1≤n,m≤k≤400。
子任务编号n≤k≤特殊性质子任务分值177无521818无5310400无104100400无255400400n=m 且最大流为 n106400400最大流为 n257400400无20
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 3 3
1 2
1 2 3
111
101
111
2 2
样例 2
2 2 4
1 2
3 4
1110
1111
1111
0111
2 9