[BOJ 23034, Python 3] 조별과제 멈춰!

https://www.acmicpc.net/problem/23034

23034번: 조별과제 멈춰!

 

 

풀이

일단 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 그래프를 구하고 팀장에서 다른 팀장으로 이동하는 경로중에 가장 큰 값을 가진 간선을 끊어주면 되는 문제로 풀 수 있게 됩니다.

 

코드

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])