문제 링크: https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 최소 스패닝 트리, 크루스칼 알고리즘 크루스칼 알고리즘으로 최소 비용으로 모든 집을 연결하고, 연결된 비용의 총합을 전체 간선의 비용 총합에서 빼주면 됩니다. #include #include #include #include #include using namespace std; const int MAX_N = 200000; vector edge; int parents[MAX_N]; int Find..

문제 링크: https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소 스패닝 트리, 크루스칼 알고리즘 모든 서로 다른 두 정점 사이에 거리를 구해서 간선에 추가하고 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 찾으면 됩니다. [주의할 점] 1. 이미 연결된 통로를 입력받을 때, 중복된 간선이 들어올 수 있습니다. 예를 들어, 1-2와 2-1은 동일한 간선을 나타냅니다. 이 경우를 고려하지 않으면 현재까지 최소 스패닝 ..

문제 링크: www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net Union-Find 알고리즘을 이용해서 기본적인 크루스칼 알고리즘을 구현하면 되는 문제입니다. 최소 스패닝 트리, 크루스칼 알고리즘 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..