[이코테] Chapter10-3 /

by


지구 계획

동물원에서 막 탈출한 원숭이가 세상을 지켜보고 있다.

어느 날 원숭이는 “평화로운 마을”에 잠시 머물렀고 마을 사람들은 도로 ​​공사 문제로 만났습니다.

마을은 N개의 집과 이를 연결하는 M개의 도로로 구성되어 있습니다.

도로는 어느 방향으로든 이동할 수 있는 편리한 도로입니다.

그리고 모든 도로에는 도로를 유지하기 위한 유지보수 비용이 있습니다.

마을 이장은 마을을 두 개의 별도 마을로 나눌 계획입니다.

혼자 관리하기에는 마을이 너무 크기 때문이다.


마을을 분할할 때 개별 마을의 집들이 서로 연결되도록 분할할 필요가 있다.

이것은 모든 단일 마을에서 두 집 사이에 항상 길이 있어야 함을 의미합니다.

마을에는 적어도 하나의 집이 있어야 합니다.

계획을 세우는 동안 촌장은 마을에 도로가 너무 많다는 생각을 했습니다.

두 마을 사이의 도로는 필요하지 않으므로 제거할 수 있습니다.

그리고 모든 단일 마을에서도 두 집 사이에 항상 길이 있도록 함으로써 더 많은 도로를 없앨 수 있습니다.


촌장은 위의 조건을 충족하기 위해 모든 도로를 제거하고 나머지 도로의 유지 관리 비용의 합을 최소화하기를 원합니다.

이것을 얻기 위한 프로그램을 작성하십시오.

입력 조건

  • 집의 수 N과 거리의 수 M은 첫 번째 줄에 주어집니다.

    N은 2 이상 100,000 이하의 정수이고, M은 1 이상 1,000,000 이하의 정수이다.

  • 다음 줄부터 M줄까지 거리 정보는 공백으로 구분된 세 개의 정수 A, B, C로 주어진다.

초기 상태

  • 첫 번째 줄에는 도로를 제거하고 남은 유지 관리 비용 합계의 최소값이 제공됩니다.

입력 예

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

출력 예

8

문제

이 문제의 핵심 아이디어는 전체 그래프에서 2개의 최소 스패닝 트리를 형성해야 한다는 것입니다.

최소 비용으로 어떻게 두 개의 스패닝 트리로 분할할 수 있습니까?

가장 간단한 방법은 Kruskal의 알고리즘을 이용하여 최소 스패닝 트리를 찾은 다음 최소 스패닝 트리를 구성하는 에지 중 가장 비싼 에지를 제거하는 것입니다.

그런 다음 최소 신장 트리를 두 개의 하위 그래프로 나누고 문제에서 요구하는 최적 솔루션을 만족합니다.


따라서 최소 스패닝 트리를 찾은 후 가장 큰 에지를 제거하는 소스 코드를 작성하면 다음과 같다.

10-8.py 샘플 응답

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    #루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent(x) !
= x:
        parent(x) = find_parent(parent, parent(x))
    return parent(x)

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent(b) = a
    else:
        parent(a) = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = (0) * (v + 1)  # 부모 테이블 초기화

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = ()
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent(i) = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()
last = 0    # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) !
= find_parent(parent, b):
        union_parent(parent, a, b)
        result = result + cost
        last = cost # 비용순으로 정렬 했으므로

print(result - last)

Related Posts: