백준 17398번: 통신망 분할
통신망 분할
아이디어
완성 상태에서 하나씩 끊어보면서 찾으면 10만 * 10만이라 풀 수 없다.
맨 처음에, 제거될 예정인 연결은 빼고 union한다. 그리고 입력받은 역순으로 연결하면서 비용을 더해준다.
코드
#include <bits/stdc++.h>
using namespace std;
int N, M, Q;
int p[100001];
pair<int, int> arr[100000];
pair<int, int> start[100000];
vector<int> v;
int find(int n) {
if (p[n] <= 0) return n;
return p[n] = find(p[n]);
}
void Union(int n1, int n2) {
n1 = find(n1);
n2 = find(n2);
if (n1 == n2) return;
else {
p[n1] += p[n2];
p[n2] = n1;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int x, y, a;
cin >> N >> M >> Q;
for (int i =0 ; i < M; i++) {
cin >> x >> y;
arr[i] = {x, y};
start[i] = {x, y};
}
for (int i = 0; i < Q; i++) {
cin >> a;
v.push_back(a-1);
start[a-1] = {-1, -1};
}
memset(p, -1, sizeof(p));
for (int i = 0; i < M; i++) {
if (start[i].first == -1) continue;
Union(arr[i].first, arr[i].second);
}
long long ans = 0;
for (auto iter = v.rbegin(); iter != v.rend(); iter++) {
if (find(arr[*iter].first) != find(arr[*iter].second)) {
ans += p[find(arr[*iter].first)]*p[find(arr[*iter].second)];
}
Union(arr[*iter].first, arr[*iter].second);
}
cout << ans;
return 0;
}
여담
비용이 int 범위를 넘어갈 수 있기 때문에 long long으로 선언해야한다. 이런 디테일이 부족한 것 같다.
Author And Source
이 문제에 관하여(백준 17398번: 통신망 분할), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-17398번-통신망-분할저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)