후보 정렬과 체인
각 모듈의 후보를 성능 오름차순으로 정렬한다. 정렬 후 성능과 소모량을 bi,j,ci,j라고 하며, 두 값은 반드시 함께 이동한다.
di,k=bi,k+1−bi,k
모듈 i마다 Ai−1개의 정점 v을 만들고 , 로 둔다. 가 쪽이면 선택한 후보 번호가 보다 크다는 뜻이다. 모든 에 대해 역방향 간선 의 용량을 무한대로 둔다. 유한한 컷에서 쪽 정점들은 접두사를 이루므로 순방향 체인 간선은 정확히 하나 잘린다. 인 모듈도 간선 하나로 표현된다.
광산의 곱 항
광산의 두 모듈을 입력 순서대로 u,v라고 하고, 선택된 성능을 Bu,Bv라고 쓰자.
−BuB
마지막 항은 ∑k,ldu,kd이다. 따라서 각 , 에 대해 에 용량 의 간선을 추가한다. 증가량이 이면 이 간선은 생략할 수 있다. 같은 두 모듈을 사용하는 광산도 각각 처리한다.
단항 비용과 답 복원
αi=
K=1+max(0,i,jmax(−q
각 1≤j≤Ai에 대해 순방향 간선 vi의 용량을 로 둔다. 이는 항상 양수이다. 후보 선택과 유한한 컷은 일대일 대응하며, 컷의 용량은 순이익의 음수에 을 더한 값이다. 따라서 최소 컷을 구하면 된다.
answer=MK−mincut−k=1∑
범위와 복잡도
정답은 −49998 이상 999999998 이하이다. αi≤10, , , 이다. 광산별 벌점 용량의 합은 이다. 모든 유한 용량의 합은 보다 작으므로 무한대 대신 를 사용한다. 모든 산술은 부호 있는 64비트 정수 범위에 들어간다.
정점 수는 V≤452, 추가하는 간선 수는 E≤82000이다. 잔여 역간선은 이 수와 별도로 저장한다. Dinic의 일반적인 시간 복잡도는 O(V2E), 공간 복잡도는 이다.
서브태스크
서브태스크 1은 모든 후보 조합을 열거한다. 시간 복잡도는 O((N+M)∏iAi)이며, 최대 개 조합이다. 서브태스크 2는 모듈마다 이진 선택 하나만 있으므로 모듈당 정점 최대 하나인 최소 컷으로 해결한다. 서브태스크 3은 전체 체인을 사용한다. 별도 정답 코드에는 를 이용한 임계값 전개도 구현하여 두 구성을 대조한다.
Solution written by GPT6