devbelly

문제 https://www.acmicpc.net/problem/23034 알고리즘 MST 풀이 MST에서 간선을 끊는 문제입니다. 조장끼리는 연락을 할 필요가 없으므로 MST에서 각 조장을 잇는 최대 간선을 끊는 문제입니다. 쿼리가 1만 개 주어지므로 미리 $N$명의 사람마다 $i$에서 $j$로 연락할 때 사용하는 최대 간선을 저장해놓으면 됩니다. 이는 $N^2$에 해결 가능하므로 쿼리마다 MST를 구성하기 위한 최소 cost에서 $dist[i][j]$를 빼주면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i > M; rep(i, M) { cin >> arr[i].u >>..

문제 www.acmicpc.net/problem/1626 알고리즘 hld, mst 풀이 MST 대신 두 번째로 작은 스패닝 트리를 구하는 문제입니다. 접근은 그리디하게 MST에서 가장 큰 간선을 제거하는 것입니다. MST를 만들 때 사용하지 않은 간선들을 검사하며 이 때 간선의 양 끝 정점을 $u, v$라고 합시다. MST를 구성했다면 $u, v$를 잇는 경로는 무조건 존재하게 됩니다. $u, v$를 연결하는 경로에서 가장 큰 간선을 제거하고 현재 사용하지 않은 간선으로 대체하며 풀어나가면 됩니다. 현재 사용하지 않은 간선의 무게와 $u, v$를 잇는 가장 큰 간선의 무게가 같은 경우가 있습니다. 이 경우는 MST가 유일하지 않은 경우입니다. 문제에서는 MST와 second MST를 다른 값으로 구분하고..