[BOJ 23034, Python 3] 조별과제 멈춰!
https://www.acmicpc.net/problem/23034
23034번: 조별과제 멈춰!
교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각
www.acmicpc.net
풀이
일단 1개의 조로 구성되어 있으면 학생들이 연락하며 소요되는 비용의 총합은 MST로 구할 수 있습니다.
하지만 문제는 2개의 조이기 때문에 시작점의 비용이 0인 곳이 두 곳이 존재합니다.
이런 그래프가 있다고 해봅시다.
여기서 MST를 빨간색으로 칠해보면 아래와 같이 나옵니다.
노란색을 팀장으로 해서 정점 두 곳을 노란색으로 칠하겠습니다.
이렇게 팀장이 있을 때, 답은 (1 + 2 + 3) + (5) = 11입니다.
비용이 4인 간선을 제외한 이유는 정점 6은 빨간 간선을 통해 정점 2, 정점 5 둘 중 아무 곳을 갈 수 있으니 그 중 큰 값인 비용이 4인 간선을 제외해도 MST를 만족하기 때문입니다.
나머지 간선은 두 가지 이유로 불가능합니다.
- 정점 1, 3은 간선을 끊는다면 정점 2, 정점 5 어느 곳도 갈 수 없기 때문에 MST를 만족할 수 없습니다.
- 정점 4에서 비용이 3인 간선을 끊는다면 답은 (1 + 2) + (4 + 5) = 12로 최솟값이 아니라서 정답이 될 수 없습니다.
그래서 이 문제는 MST 그래프를 구하고 팀장에서 다른 팀장으로 이동하는 경로중에 가장 큰 값을 가진 간선을 끊어주면 되는 문제로 풀 수 있게 됩니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
def find(x):
if x == p[x]: return p[x]
p[x] = find(p[x])
return p[x]
def merge(x, y):
x, y = find(x), find(y)
p[y] = x
return
def dfs(start, now, val):
for nx, nt in adj[now]:
if not visit[nx]:
visit[nx] = 1
dist[start][nx] = max(val, nt)
dfs(start, nx, max(val, nt))
input = __import__('sys').stdin.readline
import sys
sys.setrecursionlimit(100000)
n, m = map(int, input().split())
arr = []
adj = [[] for _ in range(n + 1)]
p = [i for i in range(n + 1)]
cost = 0
for i in range(m):
a, b, c = map(int, input().split())
arr.append([a, b, c])
arr.sort(key=lambda a: a[2])
for i in range(m):
a, b, c = arr[i]
if find(a) != find(b):
cost += c
merge(a, b)
adj[a].append([b, c])
adj[b].append([a, c])
dist = [[0] * (n+1) for _ in range(n+1)]
for i in range(n):
visit = [0] * (n + 1); visit[i+1] = 1
dfs(i+1, i+1, 0)
for i in range(int(input())):
u, v = map(int, input().split())
print(cost - dist[u][v])
|
cs |