Home » 国际竞赛 » Details

USACO 2019 US Open Contest, Platinum Problem 2. Compound Escape

Category: 国际竞赛, 计算机国际竞赛 Date: 2019年5月17日下午6:34

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 $N K$ 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$ .

INPUT FORMAT (file escape.in):

The first line contains two space-separated integers, $N$ and $K$ ( $2 \leq N \leq 30000, 2 \leq K \leq 6$ ).Each of the next $N$ lines contains $K - 1$ space-separated integers: the costs of unlocking each gate on a horizontal edge.

Each of the next $K$ lines 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 \leq 500$ and all weights are between $1$ and $5$ inclusive.

In another 20% of the test cases, it is guaranteed that $N \leq 5000$ .

OUTPUT FORMAT (file escape.out):

A single integer: the number of minimum-cost escape plans, modulo $10^{9} + 7$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

The test case presents a 4x3 grid,

     1     1
  +-----+-----+
  |     |     |
1 |     |2    | 1
  |  5  |  6  |
  +-----+-----+
  |     |     |
1 |     |3    | 1
  |  7  |  8  |
  +-----+-----+
  |     |     |
1 |     |4    | 1
  |     |     |
  +-----+-----+
     1    1

Any minimum-cost escape plan will use the doorway of cost 2, the doorway of cost 3, and some nine of the doorways of cost 1. There are ten choices for which cost-1 edge to not use, so the answer is 10.

Problem credits: Brian Dean

中文版

Bessie和她的朋友们被抓走并关在了远离农场的一个秘密房屋，现在该是Bessie站出来策划脱逃的时候了！这一房屋包含 $N K$ 个排列成 $N \times K$ 矩形方阵的囚室，水平和垂直方向相邻的囚室之间有门互通。每个囚室中有一头奶牛。

Bessie黑进了系统，可以解锁任意一部分的门，但是每个门均有其代价。为了使奶牛们能够脱逃，Bessie必须打开足够多的门使得所有的奶牛可以聚集在一个房间内（这样她们就能拥有足够的力量挖地洞通向外面！）。Bessie想要使得总的解锁花费最小。

但是这次行动异常关键，Bessie不能满足于仅仅一个脱逃方案：她还需要后备方案。帮助她计算最小代价脱逃方案的数量；如果某一扇门在一个方案中被解锁了而在另一个方案中没有，那么这两个方案就被认为是不同的。

由于这个数字可能非常大，只需输出该数对 $10^{9} + 7$ 取模的余数。

输入格式（文件名：escape.in）：

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$ （ $2 \leq N \leq 30000, 2 \leq K \leq 6$ ）。以下 $N$ 行每行包含 $K - 1$ 个空格分隔的整数，为解锁一条水平边上的每扇门需要花费的代价。

以下 $K$ 行每行包含 $N - 1$ 个空格分隔的整数，为解锁一条垂直边上的每扇门需要花费的代价。

所有的花费均在 $1$ 到 $10^{9}$ 之间。

对于20%的测试数据，保证 $N \leq 500$ ，所有的代价均在 $1$ 到 $5$ 之间。

对于另外20%的测试数据，保证 $N \leq 5000$ 。

输出格式（文件名：escape.out）：

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

输入样例：

输出样例：

这个测试样例描述了一个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