5091: USACO 2019 US Open Contest, Platinum —— Problem 2. Compound Escape
[Creator : ]
Description
Bessie and friends have been captured and are trapped in a secret compound in a
location far from their farm, and it is up to Bessie to plan their escape! The
compound consists of $NK$ holding cells arranged in an $N \times K$ rectangular
grid, where there are gates between horizontally and vertically adjacent cells.
Each cell houses exactly one cow.
Bessie has hacked into the system, and is able to unlock any subset of the gates, but each gate has a cost. For the cows to escape, Bessie must open enough gates that all the cows can gather in a single cell (so that they have enough cow-power to tunnel to the surface!). Bessie wants to minimize the total unlocking cost.
But the stakes are higher than ever, and Bessie cannot be content with just one escape plan: she needs back-ups. Help her count the number of minimum-cost escape plans; two plans are considered different if some gate needs to be unlocked in one of the plans but not the other.
Since this number may be very large, only output its remainder modulo $10^9+7$.
Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是 Bessie 站出来策划脱逃的时候了！
这一房屋包含 $NK$ 个排列成 $N\times K$ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。
Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。
但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。
由于这个数字可能非常大，只需输出该数对 $10^9+7$ 取模的余数。
Bessie has hacked into the system, and is able to unlock any subset of the gates, but each gate has a cost. For the cows to escape, Bessie must open enough gates that all the cows can gather in a single cell (so that they have enough cow-power to tunnel to the surface!). Bessie wants to minimize the total unlocking cost.
But the stakes are higher than ever, and Bessie cannot be content with just one escape plan: she needs back-ups. Help her count the number of minimum-cost escape plans; two plans are considered different if some gate needs to be unlocked in one of the plans but not the other.
Since this number may be very large, only output its remainder modulo $10^9+7$.
Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是 Bessie 站出来策划脱逃的时候了！
这一房屋包含 $NK$ 个排列成 $N\times K$ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。
Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。
但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。
由于这个数字可能非常大，只需输出该数对 $10^9+7$ 取模的余数。
Input
The first line contains two space-separated integers, $N, K\ (2 ≤ N ≤ 30000, 2 ≤ K ≤ 6)$.
Each of the next Nlines contains $K−1$ space-separated integers: the costs of unlocking each gate on a horizontal edge.
Each of the next Klines contains $N−1$ space-separated integers: the costs of unlocking each gate on a vertical edge.
All costs are between $1$ and $10^9$ inclusive.
In $20\%$ of the test cases, it is guaranteed that $N ≤ 500$ and all weights are between $1\sim 5$ inclusive.
In another $20\%$ of the test cases, it is guaranteed that $N ≤ 5000$.
输入的第一行包含两个空格分隔的整数 N 和 K。
以下 N 行每行包含 K−1 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。
以下 K 行每行包含 N−1 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。
Each of the next Nlines contains $K−1$ space-separated integers: the costs of unlocking each gate on a horizontal edge.
Each of the next Klines contains $N−1$ space-separated integers: the costs of unlocking each gate on a vertical edge.
All costs are between $1$ and $10^9$ inclusive.
In $20\%$ of the test cases, it is guaranteed that $N ≤ 500$ and all weights are between $1\sim 5$ inclusive.
In another $20\%$ of the test cases, it is guaranteed that $N ≤ 5000$.
输入的第一行包含两个空格分隔的整数 N 和 K。
以下 N 行每行包含 K−1 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。
以下 K 行每行包含 N−1 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。
Output
A single integer: the number of minimum-cost escape plans, modulo $10^9+7$.
一个整数：最小花费的逃脱方案的数量，对 $10^9+7$ 取模。
一个整数：最小花费的逃脱方案的数量，对 $10^9+7$ 取模。
Sample 1 Input
4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1
Sample 1 Output
10
这个测试样例描述了一个4x3的方阵，
1 1
+-----+-----+
| | |
1 | |2 | 1
| 5 | 6 |
+-----+-----+
| | |
1 | |3 | 1
| 7 | 8 |
+-----+-----+
| | |
1 | |4 | 1
| | |
+-----+-----+
1 1
所有的最小代价脱逃方案都会使用代价为2的门，代价为3的门，以及某九个代价为1的门。由于有十种方式选择不被使用的代价为1的门，所以答案为10。