목록Algorithm/C++ (148)
cgy12306
최소 신장 트리를 구성하고, 마지막으로 연결된 부분을 빼주면 이상적으로 마을이 두개로 분할된다. // 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..
// https://www.acmicpc.net/problem/11660 // 구간 합 구하기 5 #include using namespace std; int arr[1026][1026], dp[1026][1026]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; int sum = 0; for (int i = 1; i arr[i][j]; sum += arr[i][j]; dp[i][j] = sum; } } for (int m = 0; m > x1 >> y1 >> x2 >> y2; for (int x..
// https://www.acmicpc.net/problem/11659 // 구간 합 구하기 4 #include using namespace std; int arr[100002], dp[100002]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, M; cin >> N >> M; for (int i = 1; i > arr[i]; } int sum = 0; for (int i = 1; i > from >> to; ans = dp[to] - dp[from - 1]; cout