목록알고리즘/문제풀이 (9)
uos-machine-learning
1922 - 네트워크 연결
각 컴퓨터를 연결하는데 필요한 비용이 주어질 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구하는 문제이다. 모든 컴퓨터(모든 정점)을 연결하는 최소 스패닝 트리를 구하면 되므로, 크루스칼 알고리즘을 사용하면 된다. #include #include #include using namespace std; struct edge { int u, v, w; // 구조체 edge에서의 연산자 < 정의 bool operator < (const edge &other) { return w < other.w; } }; int parent[1001]; int find(int x) { if (x == parent[x]) { return x; } return parent[x] = find(parent[x]); } void Un..
알고리즘/문제풀이
2019. 5. 9. 23:43