https://www.acmicpc.net/problem/6497
이 문제는 그냥 크루스칼 알고리즘인데 출력이 불친절하다 그냥 00전에 테스트케이스가 여러개 나오는 문제였다
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int parent[200000];
int n, m;
vector<pair<int, pair<int, int>>> inputData;
int findParent(int x) {
if (parent[x] == x)
return x;
else
return parent[x] = findParent(parent[x]);
}
bool isSameParent(int x, int y) {
return findParent(x) == findParent(y);
}
void uni(int x, int y) {
x = findParent(x);
y = findParent(y);
parent[y] = x;
}
int main() {
while (true) {
cin >> n >> m;
if (n == 0 && m == 0) break; // 종료 조건
inputData.clear();
int tmp1, tmp2, tmp3;
int cost = 0, totalCost = 0;
for (int i = 0; i < m; i++) {
cin >> tmp1 >> tmp2 >> tmp3;
inputData.push_back({ tmp3, {tmp1, tmp2} });
totalCost += tmp3;
}
// 초기화
for (int i = 0; i < n; i++) {
parent[i] = i;
}
sort(inputData.begin(), inputData.end()); // 간선 정렬
for (int i = 0; i < inputData.size(); i++) {
if (!isSameParent(inputData[i].second.first, inputData[i].second.second)) {
uni(inputData[i].second.first, inputData[i].second.second);
cost += inputData[i].first;
}
}
cout << totalCost - cost << "\n";
}
return 0;
}
'백준(코테준비) > 그래프' 카테고리의 다른 글
백준 1005 / C++ / 위상정렬 (0) | 2025.01.26 |
---|---|
백준 2887 / C++ / 그래프 / 크루스 (0) | 2025.01.12 |
백준 2252 / CPP / 위상 정렬 (1) | 2024.12.01 |
백준 4386 / C++ (0) | 2024.08.04 |
백준 1647 / C++ (0) | 2024.08.04 |