루미 알고리즘

#1118플래티넘통행료통행료

KOI 2025 2차코딩초등부 3번출제 김기범이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

통행료

원제: 통행료

문제

KOI 도시는 11번 건물부터 NN번 건물까지 NN개의 건물로 이루어져 있으며, 11번 도로부터 MM번 도로까지 MM개의 양방향 도로가 각 건물을 연결하고 있다. 각 도로는 서로 다른 두 건물을 연결하며, 이 중 ii번 도로는 uiu_i번 건물과 viv_i번 건물을 양방향으로 연결한다. 이때, 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.

원래 KOI 도시의 각 도로는 무료로 이용할 수 있었다. 즉, 모든 도로의 통행료는 00원이었다. 그러나, KOI 도시의 시장인 정올이는 KOI 도시의 재정난을 극복하기 위해, MM일에 걸쳐 각 도로에 통행료를 부과하려고 한다. 구체적으로, 정올이는 ii번째 날에 ii번 도로의 통행료를 11원으로 변경한다. 이에 따라, MM일이 모두 지나면 모든 도로의 통행료는 11원이 될 것이다.

aa번 건물과 bb번 건물 사이의 최소 이동 비용을 aa번 건물에서 bb번 건물로 이동하기 위해 필요한 총 통행료의 최솟값으로 정의하고, f(a,b)f(a, b)로 표기하자. a=ba = b라면 f(a,b)=0f(a, b) = 0이다.

도로망의 총 비용은, 가능한 모든 두 건물의 쌍 사이의 최소 이동 비용의 합으로 정의한다. 즉, 모든 1≤a,b≤N1 \le a, b \le N인 자연수 aa와 bb에 대해 f(a,b)f(a, b)의 값을 계산한 후 이를 모두 합친 값이 도로망의 총 비용이다. 이를 수학 기호로 표기하면, 도로망의 총 비용은 ∑a=1N∑b=1Nf(a,b)\sum_{a=1}^{N} \sum_{b=1}^{N} f(a, b) 가 된다.

정올이는 통행료 변화가 시민들에게 어떤 영향을 줄지 분석하려고 한다. 당신은 정올이를 도와, ii번째 날이 끝난 이후 도로망의 총 비용을 계산해야 한다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤5002 \le N \le 500
  • N−1≤M≤N(N−1)2N - 1 \le M \le \frac{N(N-1)}{2}
  • 1≤i≤M1 \le i \le M에 대해서, ui≠viu_i \ne v_i를 만족한다.
  • 1≤i≤M1 \le i \le M에 대해서, 1≤ui,vi≤N1 \le u_i, v_i \le N을 만족한다.
  • 임의의 서로 다른 두 건물을 잇는 도로는 최대 하나이다.
  • 임의의 두 건물 사이를 도로들을 이용해 오갈 수 있다.

부분문제

  1. (10점) N≤5N \le 5.
  2. (15점) N≤50N \le 50.
  3. (30점) M≤500M \le 500.
  4. (45점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 NN과 MM이 공백으로 구분되어 주어진다.

다음 MM개의 줄에는 도로의 정보가 주어진다. 이 중 i(1≤i≤M)i(1 \le i \le M)번째 줄에는 두 정수 ui,viu_i, v_i가 공백으로 구분되어 주어진다.

출력 형식

총 MM개의 줄을 출력한다. 이 중 i(1≤i≤M)i(1 \le i \le M) 번째 줄에는, ii번째 날이 끝난 이후 도로망의 총 비용을 출력한다.

예제

예제 1

입력
4 4
1 2
2 3
3 1
3 4
출력
0
6
10
16

44일이 지난 뒤 각 건물 간의 최소 이동 비용은 다음과 같은 표로 나타낼 수 있다.

1번 건물2번 건물3번 건물4번 건물
1번 건물0112
2번 건물1012
3번 건물1101
4번 건물2210

따라서, 44번째 날이 끝난 이후 도로망의 총 비용은 0+1+1+2+1+0+1+2+1+1+0+1+2+2+1+0=160 + 1 + 1 + 2 + 1 + 0 + 1 + 2 + 1 + 1 + 0 + 1 + 2 + 2 + 1 + 0 = 16이 된다.

예제 2

입력
4 4
2 3
3 1
3 4
1 2
출력
0
8
14
16

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.