DOJ logoDOJ
문제
최근 추가된 문제들저장한 문제문제집
카테고리DLC대회그룹팀게시판
랭킹
문제 풀이 랭킹스트릭 랭킹DOJ Power 랭킹
현황
문제 제안로그인회원가입
DOJ logoDOJ

OI 서브태스크 채점, Elo 레이팅, Discord 계정 연동을 갖춘 커뮤니티 온라인 저지.

문제
문제 목록카테고리
커뮤니티
대회랭킹게시판공지사항외부 대회 개최이용 안내
계정
로그인회원가입채점 현황
정책
이용약관DLC 이용 규칙개인정보 처리방침API 사용 설명서언어별 채점 환경대회 순위 보상레이팅과 퍼포먼스
© 2026 DOJ
모든 권리 보유
해설

일하는 다다스

문제로 돌아가기

해설

후보 정렬과 체인 각 모듈의 후보를 성능 오름차순으로 정렬한다. 정렬 후 성능과 소모량을 bi,j,ci,jb_{i,j},c_{i,j}bi,j​,ci,j​라고 하며, 두 값은 반드시 함께 이동한다.

di,k=bi,k+1−bi,k≥0(1≤k<Ai).d_{i,k}=b_{i,k+1}-b_{i,k}\geq 0\qquad(1\leq k<A_i).di,k​=bi,k+1​−bi,k​

모듈 iii마다 Ai−1A_i-1Ai​−1개의 정점 vi,1,…,vi,Ai−1v_{i,1},\ldots,v_{i,A_i-1}v을 만들고 , 로 둔다. 가 쪽이면 선택한 후보 번호가 보다 크다는 뜻이다. 모든 에 대해 역방향 간선 의 용량을 무한대로 둔다. 유한한 컷에서 쪽 정점들은 접두사를 이루므로 순방향 체인 간선은 정확히 하나 잘린다. 인 모듈도 간선 하나로 표현된다.

광산의 곱 항 광산의 두 모듈을 입력 순서대로 u,vu,vu,v라고 하고, 선택된 성능을 Bu,BvB_u,B_vBu​,Bv​라고 쓰자.

−BuBv=−bv,1Bu−bu,AuBv+bu,Aubv,1+(bu,Au−Bu)(Bv−bv,1).-B_uB_v=-b_{v,1}B_u-b_{u,A_u}B_v+b_{u,A_u}b_{v,1}+(b_{u,A_u}-B_u)(B_v-b_{v,1}).−Bu​B

마지막 항은 ∑k,ldu,kdv,l[vu,k∈T][vv,l∈S]\sum_{k,l}d_{u,k}d_{v,l}[v_{u,k}\in T][v_{v,l}\in S]∑k,l​du,k​d이다. 따라서 각 , 에 대해 에 용량 의 간선을 추가한다. 증가량이 이면 이 간선은 생략할 수 있다. 같은 두 모듈을 사용하는 광산도 각각 처리한다.

단항 비용과 답 복원

αi=∑k:Uk=ibVk,1+∑k:Vk=ibUk,AUk,qi(j)=ci,j−αibi,j.\alpha_i=\sum_{k:U_k=i}b_{V_k,1}+\sum_{k:V_k=i}b_{U_k,A_{U_k}},\qquad q_i(j)=c_{i,j}-\alpha_i b_{i,j}.αi​= K=1+max⁡(0,max⁡i,j(−qi(j))).K=1+\max\left(0,\max_{i,j}(-q_i(j))\right).K=1+max(0,i,jmax​(−q

각 1≤j≤Ai1\leq j\leq A_i1≤j≤Ai​에 대해 순방향 간선 vi,j−1→vi,jv_{i,j-1}\to v_{i,j}vi의 용량을 로 둔다. 이는 항상 양수이다. 후보 선택과 유한한 컷은 일대일 대응하며, 컷의 용량은 순이익의 음수에 을 더한 값이다. 따라서 최소 컷을 구하면 된다.

answer=MK−mincut⁡−∑k=1NbUk,AUkbVk,1.\text{answer}=MK-\operatorname{mincut}-\sum_{k=1}^{N}b_{U_k,A_{U_k}}b_{V_k,1}.answer=MK−mincut−k=1∑

범위와 복잡도 정답은 −49 998-49\,998−49998 이상 999 999 998999\,999\,998999999998 이하이다. αi≤106\alpha_i\leq10^6αi​≤10, , , 이다. 광산별 벌점 용량의 합은 이다. 모든 유한 용량의 합은 보다 작으므로 무한대 대신 를 사용한다. 모든 산술은 부호 있는 64비트 정수 범위에 들어간다.

정점 수는 V≤452V\leq452V≤452, 추가하는 간선 수는 E≤82 000E\leq82\,000E≤82000이다. 잔여 역간선은 이 수와 별도로 저장한다. Dinic의 일반적인 시간 복잡도는 O(V2E)O(V^2E)O(V2E), 공간 복잡도는 이다.

서브태스크 서브태스크 1은 모든 후보 조합을 열거한다. 시간 복잡도는 O((N+M)∏iAi)O((N+M)\prod_i A_i)O((N+M)∏i​Ai​)이며, 최대 10610^6개 조합이다. 서브태스크 2는 모듈마다 이진 선택 하나만 있으므로 모듈당 정점 최대 하나인 최소 컷으로 해결한다. 서브태스크 3은 전체 체인을 사용한다. 별도 정답 코드에는 를 이용한 임계값 전개도 구현하여 두 구성을 대조한다.

Solution written by GPT6

≥
0(1≤
k<
Ai​).
i,1
​
,
…
,
vi,Ai​−1​
vi,0=Sv_{i,0}=Svi,0​=S
vi,Ai=Tv_{i,A_i}=Tvi,Ai​​=T
vi,kv_{i,k}vi,k​
SSS
kkk
1≤k≤Ai1\leq k\leq A_i1≤k≤Ai​
vi,k→vi,k−1v_{i,k}\to v_{i,k-1}vi,k​→vi,k−1​
SSS
Ai=1A_i=1Ai​=1
S→TS\to TS→T
v
​
=
−bv,1​Bu​−
bu,Au​​Bv​+
bu,Au​​bv,1​+
(bu,Au​​−
Bu​)(Bv​−
bv,1​).
v,l​
[
vu,k​
∈
T][vv,l​∈
S]
1≤k<Au1\leq k<A_u1≤k<Au​
1≤l<Av1\leq l<A_v1≤l<Av​
vv,l→vu,kv_{v,l}\to v_{u,k}vv,l​→vu,k​
du,kdv,ld_{u,k}d_{v,l}du,k​dv,l​
000
k:Uk​=i∑​
bVk​,1​
+
k:Vk​=i∑​bUk​,AUk​​​,qi​(j)=
ci,j​−
αi​bi,j​.
i​
(
j
))
)
.
,
j
−
1
​
→
vi,j​
K+qi(j)K+q_i(j)K+qi​(j)
MK−∑kbUk,AUkbVk,1MK-\sum_k b_{U_k,A_{U_k}}b_{V_k,1}MK−∑k​bUk​,AUk​​​bVk​,1​
N
​
bUk​,AUk​​​
bVk​,1​
.
6
1−109≤qi(j)≤10001-10^9\leq q_i(j)\leq10001−109≤qi​(j)≤1000
K≤109K\leq10^9K≤109
MK≤5⋅1010MK\leq5\cdot10^{10}MK≤5⋅1010
(bu,Au−bu,1)(bv,Av−bv,1)≤9992(b_{u,A_u}-b_{u,1})(b_{v,A_v}-b_{v,1})\leq999^2(bu,Au​​−bu,1​)(bv,Av​​−bv,1​)≤9992
5.01⋅10115.01\cdot10^{11}5.01⋅1011
101510^{15}1015
O(V+E)O(V+E)
O(V+E)
106
−wxy=wx(1−y)−wx-wxy=wx(1-y)-wx−wxy=wx(1−y)−wx