목록최소 스패닝 트리 (9)

1일1알

백준 4386번 별자리 만들기 C++

모든 별끼리 서로 연결될 수 있기 때문에 이어질수 있는 모든 경로를 후보로 두고 거리가 작은 순서로 정렬한 뒤 최소 스패닝 트리를 이용하여 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; struct Pos { int head; double x; double y; }; struct LoadInfo { Pos start; Pos end; double dist; bool operator height[..
알고리즘 2022. 7. 10. 14:32
백준 1647번 도시 분할 계획 C++

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리를 구하고 최소 스패닝 트리로 연결된 길 중에서 유지비의 값이 가장 높은 길을 빼면 된다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; struct LoadInfo { int start; int end; int cost; bool operator height[v]) ::swap(u, v); parent[u] = v; if (height[u] == ..
알고리즘 2022. 7. 9. 14:59
백준 1197번 최소 스패닝 트리 C++

유니온 파인드와 크루스칼 알고리즘을 이용해서 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; struct RouteCost { int start; int end; int cost; bool operator height[v]) swap(u, v); parent[u] = v; if (height[u] == height[v]) height[v]++; } int main() { ios_base::sync_with_s..
알고리즘 2022. 7. 2. 11:15
이전 Prev 1 2 Next 다음