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)
- {
- return parent[x];
- }
- void unionx(int x, int y, int* parent, int n)
- {
- int rep_x=parent[x];
- int rep_y=parent[y];
- if(rep_x==rep_y) return;
- for(int i=0; i<=n; i++){
- if(rep_x==parent[i]){
- parent[i]=rep_y;
- }
- }
- }
- 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;// ????;
- }
- for (int i = 0; i < n-1; i++) {
- edge e;
- do {
- e = Q.top(); Q.pop();
- } while (find(e.u,parent)==find(e.v,parent));
- cost+=e.s;
- unionx(e.u, e.v,parent, n);
- }
- return cost;
- }
- int main ()
- {
- int Z;
- scanf("%d", &Z);
- while(Z--)
- {
- int n, m;
- scanf ("%d %d", &n, &m);
- edge temp;
- int u, v, s;
- priority_queue<edge> Q;
- for (int i = 0; i < m; i++)
- {
- scanf("%d %d %d", &u, &v, &s);
- edge e={u,v,s};
- Q.push(e);
- }
- unsigned long long cost = mst(Q, n);
- printf ("%llu\n", cost);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement