Compound Escape

题目描述

Bessie 和她的朋友们被抓住并困在一个远离农场的秘密基地里，Bessie 必须为她们策划逃脱！基地由 $NK$ 个牢房组成，排列成一个 $N \times K$ 的长方形网格；水平和竖直相邻的牢房之间都有门。每个牢房里恰好住着一头奶牛。 Bessie 入侵了系统，可以解锁任意一部分门，但每扇门都有解锁成本。为了让奶牛们逃脱，Bessie 必须打开足够多的门，使得所有奶牛都能聚集到同一个牢房里（这样它们才有足够的“牛力”挖到地面！）。Bessie 希望将总解锁成本最小化。 但形势空前严峻，Bessie 不能只满足于一个逃脱方案：她需要备选方案。请你帮助她统计最小成本逃脱方案的数量；如果两种方案中存在某一扇门在其中一种方案需要解锁而另一种不需要，则认为这两种方案不同。 由于该数量可能非常大，只需输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$（$2 \le N \le 30000, 2 \le K \le 6$）。 接下来 $N$ 行，每行包含 $K-1$ 个用空格分隔的整数：每一条水平边上对应门的解锁成本。 接下来 $K$ 行，每行包含 $N-1$ 个用空格分隔的整数：每一条竖直边上对应门的解锁成本。 所有成本均在 $1$ 到 $10^9$（含）之间。

输出格式

输出一个整数：最小成本逃脱方案的数量，对 $10^{9} + 7$ 取模。

4 3
1 1
5 6
7 8
1 1
1 1 1
2 3 4
1 1 1

10

提示

在 20% 的测试数据中，保证 $N \leq 500$ 且所有权值均在 $1$ 到 $5$（含）之间。 另有 20% 的测试数据中，保证 $N \leq 5000$。 该测试用例给出了一个 4x3 的网格， 1 1 +-----+-----+ | | | 1 | |2 | 1 | 5 | 6 | +-----+-----+ | | | 1 | |3 | 1 | 7 | 8 | +-----+-----+ | | | 1 | |4 | 1 | | | +-----+-----+ 1 1 任何一个最小成本的逃脱方案都会使用成本为 2 的门、成本为 3 的门，以及成本为 1 的门中的某九个。一共有十种选择来决定不使用哪一条成本为 1 的边，所以答案是 10。 题目鸣谢：Brian Dean

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum