RiseOJ – 수용소 탈출

설명

베시와 친구들이 붙잡혀 농장에서 멀리 떨어진 비밀 수용소에 갇혔다. 탈출 계획을 세우는 것은 베시의 몫이다! 수용소는 $N \times K$ 직사각형 격자로 배열된 $$NK$$ 개의 감방으로 이루어져 있으며, 가로 또는 세로로 인접한 감방 사이에는 문이 있다. 각 감방에는 정확히 한 마리의 소가 갇혀 있다.

베시는 시스템을 해킹하여 문들의 임의의 부분집합을 열 수 있지만, 각 문을 여는 데는 비용이 든다. 소들이 탈출하려면, 모든 소가 하나의 감방에 모일 수 있을 만큼 충분한 문을 열어야 한다(그래야 지표면까지 터널을 팔 만큼의 소 파워가 모인다!). 베시는 총 잠금 해제 비용을 최소화하고 싶다.

하지만 그 어느 때보다 위험 부담이 크기에, 베시는 탈출 계획 하나로 만족할 수 없다. 예비 계획이 필요하다. 최소 비용 탈출 계획의 수를 세는 것을 도와주자. 두 계획은 한 계획에서는 열어야 하지만 다른 계획에서는 열 필요가 없는 문이 존재할 때 서로 다른 것으로 간주한다.

이 수는 매우 클 수 있으므로, $$10^9 + 7$$ 로 나눈 나머지만 출력한다.

문제 제공: Brian Dean

제약

문제 제공: Brian Dean

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$N$$ 과 $$K$$ 가 주어진다 ( $2 \le N \le 30000, 2 \le K \le 6$ ).

다음 $$N$$ 개의 줄 각각에는 공백으로 구분된 $$K-1$$ 개의 정수가 주어진다: 가로 간선 위의 각 문을 여는 비용이다.

다음 $$K$$ 개의 줄 각각에는 공백으로 구분된 $$N-1$$ 개의 정수가 주어진다: 세로 간선 위의 각 문을 여는 비용이다.

모든 비용은 $$1$$ 이상 $$10^9$$ 이하이다.

20%의 테스트 케이스에서는 $N \leq 500$ 이고 모든 가중치가 $$1$$ 이상 $$5$$ 이하임이 보장된다.

다른 20%의 테스트 케이스에서는 $N \leq 5000$ 이 보장된다.

출력 형식

하나의 정수를 출력한다: 최소 비용 탈출 계획의 수를 $10^{9} + 7$ 로 나눈 나머지이다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 escape.in · 출력을 쓸 파일 escape.out

예제 1

입력

출력

설명

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.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > US Open > Platinum

올림피아드 > USACO > 2018-2019 > US Open > Platinum

태그

JudgeUSACO

수용소 탈출

평가 및 의견

풀이 제출