Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <cstdio>
- #include <utility>
- #include <vector>
- #define ULL unsigned long long
- #define LL long long
- #define uint unsigned int
- uint sz_max = 1;
- typedef struct {
- uint a;
- uint b;
- uint c;
- } line;
- bool comp(line x, line y) { return x.c < y.c; }
- std::vector<uint> p, sz;
- // O(log(n))
- uint get(uint v) {
- if (v == p[v])
- return v;
- p[v] = get(p[v]);
- return p[v];
- }
- bool check(uint v, uint u) {
- if (get(v) == get(u))
- return true;
- else
- return false;
- }
- bool unite(uint v, uint u) {
- int x = get(v);
- int y = get(u);
- if (x == y)
- return false;
- if (sz[x] > sz[y])
- std::swap(x, y);
- p[x] = y;
- sz[y] += sz[x];
- if (sz[y] > sz_max) {
- sz_max = sz[y];
- }
- return true;
- }
- int main() {
- uint n = 0;
- scanf("%u", &n);
- p.resize(n, 0);
- sz.resize(n, 0);
- uint n_cmp = n;
- for (uint i = 0; i < n; i++) {
- p[i] = i;
- sz[i] = 1;
- }
- uint m;
- scanf("%u", &m);
- std::vector<line> lines(m);
- for (uint i = 0; i < m; i++) {
- scanf("%u %u %u", &lines[i].a, &lines[i].b, &lines[i].c);
- lines[i].a--;
- lines[i].b--;
- // if (unite(lines[i].a, lines[i].b)) {
- // n_cmp--;
- // }
- // printf("%u %u\n", n_cmp, sz_max);
- }
- ULL total_cost = 0;
- std::sort(lines.begin(), lines.end(), comp);
- for (line line : lines) {
- if (get(line.a) != get(line.b)) {
- unite(line.a, line.b);
- total_cost += line.c;
- n_cmp--;
- }
- }
- if (n_cmp != 1) {
- printf("IMPOSSIBLE");
- return 0;
- }
- printf("%llu\n", total_cost);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement