Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <queue>
- using namespace std;
- struct edge
- {
- int u, v;
- int s;
- };
- // this is called operator overload
- // we can now use operator < with edges
- // priority_queue<edge> will also use this operator to sort edges
- bool operator< (edge a, edge b)
- {
- if (a.s > b.s)
- return true;
- else
- return false;
- }
- int find (int x, int* parent)
- {
- while(parent[x] != x) {
- parent[x] = parent[parent[x]];
- x = parent[x];
- }
- return x;
- }
- void uni(int x, int y, int* parent)
- {
- int rootX = find(x, parent);
- int rootY = find(y, parent);
- parent[rootX] = rootY;
- }
- unsigned long long mst(priority_queue<edge> Q, int n)
- {
- unsigned long long cost = 0;
- int *parent = new int[n+1];
- for (int i = 0; i <= n; i++) {
- parent[i] = i;
- }
- while(!Q.empty() && n > 1) {
- edge e = Q.top(); Q.pop();
- int parentU = find(e.u, parent);
- int parentV = find(e.v, parent);
- if(parentU != parentV) {
- cost += e.s;
- uni(parentU, parentV, parent);
- }
- }
- return cost;
- }
- int main ()
- {
- int Z;
- scanf("%d", &Z);
- while(Z--)
- {
- int n, m;
- scanf ("%d %d", &n, &m);
- int u, v, s;
- priority_queue<edge> Q;
- for (int i = 0; i < m; i++)
- {
- edge temp;
- scanf("%d %d %d", &u, &v, &s);
- temp.s = s;
- temp.u = u;
- temp.v = v;
- Q.push(temp);
- }
- unsigned long long cost = mst(Q, n);
- printf ("%llu\n", cost);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement