목록전체 글 (370)
cgy12306
// https://www.acmicpc.net/problem/9372 // 상근이의 여행 #include #include #include #include using namespace std; vector edges; int parent[1002]; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruskal() { int cnt = 0; for (auto e : edges) { int a = e.first; i..
// https://www.acmicpc.net/problem/1774 // 우주신과의 교감 #include #include #include #include #include using namespace std; int N, M; int parent[1002]; vector god; vector path; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void kruskal() { double sum = 0; for (au..
별의 입력 개수가 100개여서 2중 반복문을 통하여 각 별들의 거리를 구해준 다음 거리를 오름차순으로 정렬한뒤 kruskal을 이용해 별들의 거리를 구함 // https://www.acmicpc.net/problem/4386 // 별자리 만들기 #include #include #include #include #include using namespace std; int N; int parent[101]; vector star; vector nebula; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (..
// https://www.acmicpc.net/problem/6497 // 전력난 #include #include #include #include #include using namespace std; int M, N, parent[200001], Msum; vector city; bool cmp(tuple a, tuple b) { return get(a) < get(b); } int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; ..
최소 신장 트리를 구성하고, 마지막으로 연결된 부분을 빼주면 이상적으로 마을이 두개로 분할된다. // https://www.acmicpc.net/problem/1647 // 도시 분할 계획 #include #include #include #include using namespace std; int N, M, parent[100002]; vector town; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b) parent[b] = a; else parent[a] = b; } void krus..
// https://www.acmicpc.net/problem/1197 // 최소 스패닝 트리 #include #include #include #include using namespace std; int V, E; vector Edges; int parent[10002]; bool cmp(tuple a, tuple b) { return get(a) < get(b); } int Find(int x) { if (parent[x] == x)return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a < b)parent[b] = a; else parent[a] = b; } void ..
// https://www.acmicpc.net/problem/1922 // 네트워크 연결 #include #include #include using namespace std; int N, M; bool visited[1002]; vector edges; priority_queue pq; int ans = 0; void prim(int start) { visited[start] = true; for (auto e : edges[start]) { int cost = e.second; int to = e.first; pq.push(make_pair(-cost, to)); } while (!pq.empty()) { int cost = -pq.top().first; int to = pq.top().second;..
// https://www.acmicpc.net/problem/1717 // 집합의 표현 #include using namespace std; int N, M; int parent[1000002]; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a > N >> M; for (int i =..
// https://www.acmicpc.net/problem/1976 // 여행 가자 #include using namespace std; int N, M, city[202][202], parent[202]; int Find(int x) { if (parent[x] == x) return x; return parent[x] = Find(parent[x]); } void Union(int a, int b) { a = Find(a); b = Find(b); if (a > N >> M; for (..
최종합 = 여태까지 더해진 값 - 색깔별 합 - 크기별 합 + 자신의 크기 문제를 지렁이 게임처럼 색깔이 다른 사이즈의 공을 흡수하는 것으로 오해하여 오래걸렸다. 그냥 단순하게 같은 색깔 전부 빼고, 같은 사이즈 전부 빼준 뒤 자신을 한번 더 더해주면 되는 문제였다. 자신을 한번 더해주는 이유는 자기 자신을 두번 뺄수는 없기 때문. // https://www.acmicpc.net/problem/10800 // 컬러볼 #include #include #include using namespace std; int cdp[200001], sdp[200001]; struct ball { int number, size, color, psum; }; bool cmp(ball a, ball b) { if (a.size..