Counting Maximum Flows in a Special Directed Grid Network

We are given three positive integers (n,m,k), a sequence of (n) positive integers (a_1,a_2,\dots,a_n), a sequence of (m) positive integers (b_1,b_2,\dots,b_m), and a (k\times k) binary (0–1) matrix (s=[s_{i,j}]_{1\le i,j\le k}).

Define a directed graph (G=(V,E)) as follows. The set of vertices is [ V = {S,T} \cup \Big( {0,1}\times {(i,j):1\le i,j\le k} \Big). ] Every grid cell ((i,j)) for (1\le i,j\le k) is split into two nodes: an "entry" node ((0,i,j)) and an "exit" node ((1,i,j)).

The edge set (E) is the union of three parts:

• \(E_1 = \{ (S, (0,1,a_i)) : 1\le i\le n \} \cup \{ ((1,k,b_i), T) : 1\le i\le m \}\);
• \(E_2 = \{ ((1,i,j),(0,i+1,j)) : 1\le i<k,\;1\le j\le k \} \cup \{ ((1,i,j),(0,i,j+1)) : 1\le i\le k, \;1\le j<k \}\);
• \(E_3 = \{ ((0,i,j),(1,i,j)) : 1\le i,j\le k \text{ and } s_{i,j}=1 \}\).

Every edge has capacity \(1\). We now treat \(G\) as a flow network with source \(S\) and sink \(T\).

Your task is to compute two quantities:

1. The value of the maximum \(S\)-\(T\) flow.
2. The number of different maximum flows. Two flows are considered different if and only if there is an edge whose flow value differs between them.

Note that in this network every valid flow (with integer flows, and since all capacities are \(1\)) decomposes into a set of edge–disjoint \(S\)-\(T\) paths. Hence, the problem reduces to counting the number of ways to choose a collection of disjoint \(S\)-\(T\) paths of maximum cardinality.

inputFormat

The input consists of several lines. The first line contains three integers (n), (m), and (k).

The second line contains (n) positive integers: (a_1,a_2,\dots,a_n). (It is guaranteed that (1\le a_i\le k)).

The third line contains (m) positive integers: (b_1,b_2,\dots,b_m). (It is guaranteed that (1\le b_i\le k)).

Then follow (k) lines, each containing (k) space–separated integers (either 0 or 1) representing the matrix (s).

outputFormat

Output two integers separated by a space: the maximum flow value and the number of different maximum flows.

sample

1 1 1
1
1
1

1 1