Pie Max Flow
시간 제한1초메모리 제한256 MB
용량 A의 스포크 N개와 용량 B의 림 순환 경로로 이루어진 휠 그래프에서 정점 0에서 각 꼭짓점 i로의 최대 유량을 구해 모두 더합니다.
문제
정점이 N + 1개 있고 0번부터 N번까지 번호가 붙어 있는 그래프가 있다. 1 ≤ i ≤ N인 각 i에 대해, 용량 Ai인 간선이 정점 0과 정점 N을 연결한다. 1 ≤ i ≤ N인 각 i에 대해, 용량 Bi인 간선이 정점 i와 정점 ((i mod N) + 1)을 연결한다. 그래프에는 이 외의 간선이 없다. 모든 간선은 무향이다.
그래프의 근원 정점 s에서 싱크 정점 t로 가는 흐름은 각 간선 e = (v1, v2)에 방향(v1 → v2 또는 v2 → v1)과 0 ≤ Fe ≤ Ke를 만족하는 수 Fe를 부여한다. 여기서 Ke는 간선 e의 용량이다. 지정된 방향으로 Fe만큼의 흐름이 흐르며, 이는 한쪽 정점에서 나가고 다른 쪽 정점으로 들어간다. 모든 흐름은 근원과 싱크를 제외한 각 정점 v에서 나가는 흐름의 합과 들어오는 흐름의 합이 같아야 한다. s에서 t로 가는 최대 흐름은 s에서 나가는 흐름의 합에서 s로 들어오는 흐름의 합을 뺀 값의, s에서 t로 가는 모든 흐름에 대한 최댓값이다.
Ci를 정점 0에서 정점 i로 가는 최대 흐름이라 하자. C1 + · · · + CN의 값을 구하라.
수열 A와 B는 직접 주어지지 않는다. 대신 N, A1, B1과 정수 P, Q, W, X가 주어진다. 그러면 i > 1에 대해:
- Ai = (PAi−1) mod Q
- Bi = (WBi−1) mod X
입력
첫째 줄에 정수 N (2 ≤ N ≤ 220)이 주어진다.
둘째 줄에 세 정수 A1, P, Q (1 ≤ A1, P, Q ≤ 229)가 주어진다.
셋째 줄에 세 정수 B1, W, X (1 ≤ B1, W, X ≤ 229)가 주어진다.
출력
한 줄에 정수 하나를 출력한다. 이는 C1 + · · · + CN의 값이다.
힌트
첫 번째 예시에서 A = [7, 1, 2, 4, 8], B = [5, 4, 1, 3, 9], C = [20, 9, 7, 8, 20]이다. 그래프는 아래와 같다.
