10423 전기가 부족해

10423 전기가 부족해 https://www.acmicpc.net/problem/10423

도시와 간선이 주어진다.
도시 중에는 발전소가 있어 전기를 공급해준다.
모든도시에 전기를 공급할 수 있는 최소 비용을 구하는 문제이다.

딱봐도 MST문제다.
도시에 전기가 공급됬는지 배열을 만들어 전기가 공급된 도시와 연결되면 갱신해주었다.
전기가 공급된 도시들의 합이 총 도시 개수이면 중지시킨다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define mp(a,b) make_pair(a,b) int N, M, K; bool elect[1001]; bool connect[1001]; int par[1001], Size[1001]; vector<pair<int,pair<int, int>>> adj; int find(int x) {     if (par[x] == x) return x;     return par[x] = find(par[x]); } bool merge(int u, int v, int &cnt) {     int nu = find(u), nv = find(v);     if (elect[u]) connect[nu] = connect[u] = true;     if (elect[v]) connect[nv] = connect[v] = true;     if (nu == nv) return false;     if (connect[nu] && connect[nv]) return false;     if (!connect[nu] && !connect[nv]) {         par[nv] = nu;         Size[nu] += Size[nv];         Size[nv] = 1;     }     else {     //적어도 한개가 연결이 안되있을 때         if (connect[nu]) {             connect[nv] = true;             cnt += Size[nv];             par[nv] = nu;             Size[nu] += Size[nv];             Size[nv] = 1;         }         else if (connect[nv]) {             connect[nu] = true;             cnt += Size[nu];             par[nu] = nv;             Size[nv] += Size[nu];             Size[nu] = 1;         }     }     return true; } int main() {     scanf("%d%d%d", &N, &M, &K);     for (int n = 1;n <= N;n++) par[n] = n, Size[n] = 1;     for (int k = 0;k < K;k++) {         int u;         scanf("%d", &u);         elect[u] = true;     }     for (int m = 0;m < M;m++) {         int u, v, w;         scanf("%d%d%d", &u, &v, &w);         adj.emplace_back(mp(w, mp(u, v)));     }     sort(adj.begin(), adj.end());     int cnt = 0, ans = 0;     for (auto &edge : adj) {         int cost = edge.first;         int u = edge.second.first, v = edge.second.second;         if (merge(u, v, cnt)) {             ans += cost;             if (cnt == N) break;         }     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

사실 더 간단하게 발전소들을 묶어 하나의 집합으로 넣어주고 MST를 구하면 된다.

#include <cstdio> #include <vector> #include <algorithm> using namespace std; #define mp(a,b) make_pair(a,b) int N, M, K; const int save = 0; bool elect[1001]; bool connect[1001]; int par[1001], Rank[1001]; vector<pair<int, pair<int, int>>> adj; int find(int x) {     if (par[x] == x) return x;     return par[x] = find(par[x]); } bool merge(int u, int v) {     u = find(u), v = find(v);     if (u == v) return false;     if (Rank[u] > Rank[v]) swap(u, v);     if (Rank[u] == Rank[v]) Rank[v]++;     Rank[v] += Rank[u];     par[u] = v;     return true; } int main() {     scanf("%d%d%d", &N, &M, &K);     for (int n = 1;n <= N;n++) par[n] = n, Rank[n] = 1;     for (int k = 0;k < K;k++) {         int u;         scanf("%d", &u);         par[u] = save;    //발전소들을 한 묶음으로 저장     }     for (int m = 0;m < M;m++) {         int u, v, w;         scanf("%d%d%d", &u, &v, &w);         adj.emplace_back(mp(w, mp(u, v)));     }     sort(adj.begin(), adj.end());     int cnt = 0, ans = 0;     for (auto &edge : adj) {         int cost = edge.first;         int u = edge.second.first, v = edge.second.second;         if (merge(u, v)) {             ans += cost;             ++cnt;             if (cnt == N - K + 1) break;         }     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs