C++ / 14950 / 정복자 ( 최소 스패닝 트리 )

https://www.acmicpc.net/problem/14950문제 요약서강 나라는 N개의 도시와 M개의 도로로 이루어졌습니다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있습니다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재합니다. 각각 도시는 1번부터 N번까지 번호가 붙여져 있습니다. 그 중에서 1번 도시의 군주 박건은 모든 도시를 정복하고 싶어합니다.처음 점거하고 있는 도시는 1번 도시 뿐입니다. 만약 특정 도시 B를 정복하고 싶다면, B와 도로로 연결된 도시들 중에서 적어도 하나를 정복하고 있어야 합니다. 조건을 만족하는 도시 중에서 하나인 A를 선택하면, B를 정복하는 과정에서 A와 B를 연결하는 도로의 비용이 소모됩니다. 박건은 한번에 하나의 도시..

• format_list_bulleted Minimum Spanning Tree
• · 2025. 4. 24.
• textsms

C++ / 21924 /도시 건설 ( 최소 스패닝 트리 )

https://www.acmicpc.net/problem/21924문제 요약채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠습니다.공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했습니다.채완이는 공사하는 데 드는 비용을 아끼려고 합니다. 모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 합니다. 위 그림에서 건물과 직선으로 표시된 도로, 해당 도로를 만들 때 드는 비용을 표시해놓은 지도입니다. 그림에 있는 도로를 다 설치할 때 드는 비용은 62입니다. 모든 건물을 연결하는 도로만 만드는 비용은 27로 절약하는 비용은 35입니다.채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있습니다.채완이를 대신해 얼마나 절약이 되는지 계산해야합니다..

• format_list_bulleted Minimum Spanning Tree
• · 2025. 4. 20.
• textsms

C++ / 1197 /최소 스패닝 트리 ( 최소 스패닝 트리 )

https://www.acmicpc.net/problem/1197문제 요약그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성해야합니다..최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말합니다. 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어집니다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어집니다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미입니다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않습니다.그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정..

• format_list_bulleted Minimum Spanning Tree
• · 2025. 4. 11.
• textsms