Home » 國際競賽 » Details

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

Category: 國際競賽, 計(jì)算機(jī)國際競賽 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和她的朋友們被抓走并關(guān)在了遠(yuǎn)離農(nóng)場的一個(gè)秘密房屋，現(xiàn)在該是Bessie站出來策劃脫逃的時(shí)候了！這一房屋包含 $N K$ 個(gè)排列成 $N \times K$ 矩形方陣的囚室，水平和垂直方向相鄰的囚室之間有門互通。每個(gè)囚室中有一頭奶牛。

Bessie黑進(jìn)了系統(tǒng)，可以解鎖任意一部分的門，但是每個(gè)門均有其代價(jià)。為了使奶牛們能夠脫逃，Bessie必須打開足夠多的門使得所有的奶?？梢跃奂谝粋€(gè)房間內(nèi)（這樣她們就能擁有足夠的力量挖地洞通向外面?。?。Bessie想要使得總的解鎖花費(fèi)最小。

但是這次行動(dòng)異常關(guān)鍵，Bessie不能滿足于僅僅一個(gè)脫逃方案：她還需要后備方案。幫助她計(jì)算最小代價(jià)脫逃方案的數(shù)量；如果某一扇門在一個(gè)方案中被解鎖了而在另一個(gè)方案中沒有，那么這兩個(gè)方案就被認(rèn)為是不同的。

由于這個(gè)數(shù)字可能非常大，只需輸出該數(shù)對 $10^{9} + 7$ 取模的余數(shù)。

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

輸入的第一行包含兩個(gè)空格分隔的整數(shù) $N$ 和 $K$ （ $2 \leq N \leq 30000, 2 \leq K \leq 6$ ）。以下 $N$ 行每行包含 $K ? 1$ 個(gè)空格分隔的整數(shù)，為解鎖一條水平邊上的每扇門需要花費(fèi)的代價(jià)。

以下 $K$ 行每行包含 $N ? 1$ 個(gè)空格分隔的整數(shù)，為解鎖一條垂直邊上的每扇門需要花費(fèi)的代價(jià)。

所有的花費(fèi)均在 $1$ 到 $10^{9}$ 之間。

對于20%的測試數(shù)據(jù)，保證 $N \leq 500$ ，所有的代價(jià)均在 $1$ 到 $5$ 之間。

對于另外20%的測試數(shù)據(jù)，保證 $N \leq 5000$ 。

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

一個(gè)整數(shù)：最小花費(fèi)的逃脫方案的數(shù)量，對 $10^{9} + 7$ 取模。

輸入樣例：

輸出樣例：

這個(gè)測試樣例描述了一個(gè)4x3的方陣，

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

所有的最小代價(jià)脫逃方案都會(huì)使用代價(jià)為2的門，代價(jià)為3的門，以及某九個(gè)代價(jià)為1的門。由于有十種方式選擇不被使用的代價(jià)為1的門，所以答案為10。

供題：Brian Dean