-
[KATTIS] Grid MST
Grid MST 풀이 문제가 좋아서 가져왔다. 1000*1000 크기의 격자에 N(100,000)개의 점이 있다. 모든 점쌍 사이에 가중치가 w(두 점 사이의 맨하탄 거리)인 간선이 있다. 이 때, 이 그래프에서 만들 수 있는 MST의 최소 가중치 합은? 정점 10만개짜리 완전그래프이기에, 나이브한 방법으로 문제를 풀기에는 꽤나 어려워 보인다. MST를 구성하는 상황을 생각해 보자. a-b와 b-c가 있고, b를 지나는 것이 최단인 a-c가 존재한다면, a-c를 MST에 포함시키는 것 보다 더 나은 방법(a-b, b-c)이 항상 존재한다. 격자의 크기가 최대 1000*1000임에 주목하자. 우리는...
-
[BOJ] 1414 : 불우이웃돕기
1414 : 불우이웃돕기 풀이 미니멈 스패닝 트리를 쓰자. 크루스칼을 쓰자. 전체 랜선의 합에서 최소로 잇는 랜선의 합을 빼주자. 자잘한 처리가 조금 귀찮은 문제다. 코드 #include <stdio.h> #include <algorithm> #include <vector> using namespace std; struct edg { int x, y, w; edg(int x, int y, int w) :x(x), y(y), w(w) {} bool operator <(edg A)const { return w < A.w; } }; int n, pnt[101]; vector<edg> gph; int find(int u) { if (u == pnt[u]) return...
-
[BOJ] 1922 : 네트워크 연결
1922 : 네트워크 연결 풀이 계절이 지나가는 하늘에는 가을로 가득 차 있습니다. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e3 + 1; const int m_ = 1e5 + 1; struct node { int u, v, w; } edg[m_]; int p[n_]; inline int find(int u) { if (u == p[u]) return u; return p[u] = find(p[u]); } void merge(int u, int v) { u = find(u), v = find(v);...
-
[BOJ] 1197 : 최소 스패닝 트리
1197 : 최소 스패닝 트리 풀이 크루스칼을 하자. 코드 #include <stdio.h> #include <vector> #include <algorithm> using namespace std; const int n_ = 1e4 + 1; const int m_ = 1e5 + 1; struct node { int u, v, c; bool operator <(node A)const { return c < A.c; } } edg[m_]; int n, m; int mom[n_]; int find(int u) { if (u == mom[u]) return u; return mom[u] = find(mom[u]); } void merge(int u, int...