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

1일1알

백준 16398번 행성 연결 C++

https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 유니온 파인드 자료구조를이용해서 최소 스패닝 트리를 구한다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long;..
알고리즘 2023. 3. 7. 19:19
백준 1774번 우주신과의 교감 C++

https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 유니온 파인드 자료구조를 이용해서 최소 스패닝 트리로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using in..
알고리즘 2022. 12. 10. 14:15
백준 13905번 세부 C++

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 최소 스패닝 트리 응용해서 최대 스패닝 트리 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int6..
알고리즘 2022. 10. 31. 15:39
백준 6497번 전력난 C++

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리를 구하여 절약할 수 있는 최대 비용을 구했다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; struct Info { int house1; int house2; int dist; bool operator(const Info& other) const { return dist > other.dist; } }; vector parent; vector he..
알고리즘 2022. 8. 30. 10:11
백준 1922번 네트워크 연결 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 Computer { int a; int b; int cost; bool operator height[v]) ::swap(u, v); parent[u] = v; if (height[u] == height[v]) height[v]++; } int main() { io..
알고리즘 2022. 8. 9. 09:49
백준 21924번 도시 건설 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 Info { int a; int b; int cost; bool operator height[v]) ::swap(u, v); parent[u] = parent[v]; if (height[u] == height[v]) height[v]++; } int main() { ios_base::s..
알고리즘 2022. 8. 5. 12:43
이전 Prev 1 2 Next 다음