MST2 codeforces #597 div2 D - Shichikuji and Power Grid ( MST ) https://codeforces.com/contest/1245/problem/D 도시(최대 2000)마다 좌표, 파워설치비용, 간선연결가중치가 주어진다. 0번도시를 dummy vertex로 두고, 이 도시랑 연결하는 비용을 파워 설치 비용으로 둔 후, 모든 간선을 정렬하여 mst를 수행한다. mst를 뽑을 때 한 쪽 정점이 0번도시라면 그 도시는 파워를 설치한 도시이고, 양쪽 다 0번이 아니라면 두 도시는 연결된 도시이다. #include #include #include #include using namespace std; typedef pair P; typedef long long ll; const int MAX = 2001; struct Edge { int u, v; ll w; Edge(int u1.. 2019. 11. 4. 최소 스패닝 트리 크루스칼 O(ElogE) 필요한 것: union-find (merge 병합성공여부 반환) 간선구조체 - 가중치 기준으로 오름차순 정렬하기 위함. int uf[100001]; int find(int a) { if (uf[a] < 0) return a; return uf[a] = find(uf[a]); } bool merge(int a, int b) { a = find(a); b = find(b); if (a == b) return false; uf[a] = b; return true; } struct Edge { int u, v, w; Edge(int u1, int v1, int w1) : u(u1), v(v1), w(w1) {} bool operator < (const Edge& O) const { re.. 2019. 8. 18. 이전 1 다음