Решение задачи №1387 «Остовное дерево» с ACMP





Решение задачи №1387 «Остовное дерево» с ACMP

Условие задачи

Требуется найти в связном неориентированном графе остовное дерево минимального веса.

Входные данные
Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество вершин и ребер графа соответственно (1 ≤ N ≤ 20 000, 0 ≤ M ≤ 100 000). Следующие M строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами Bi, Ei и Wi – номера концов ребра и его вес соответственно (1 ≤ Bi, Ei ≤ N, 0 ≤ Wi ≤ 100 000).

Выходные данные
В выходной файл OUTPUT.TXT выведите целое число – вес минимального остовного дерева.

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<cstdlib>
#define MP make_pair
using namespace std;
vector<int> p;
int find_set(int x){return(x==p[x])?x:p[x]=find_set(p[x]);}
void unite_set(int x, int y){
x=find_set(x);y=find_set(y);if(x==y)return;
if(rand()%2)swap(x,y);
p[x]=y;}
int main(){
int n,m,i,j,k,s=0,w;long long ans=0;
cin>>n>>m;
p.resize(n+1);for(k=1;k<=n;++k)p[k]=k;
pair<int,pair<int, int>>r[m];
for(k=0;k<m;++k){cin>>i>>j>>w;r[k]=MP(w,MP(i,j));}
sort(r, r+m);
for(k=0;k<m&&s<n-1;++k){
i=find_set(r[k].second.first);
j=find_set(r[k].second.second);
if(i!=j){
ans+=r[k].first;s++;unite_set(i,j);}}
cout<<ans;
return 0;}



Условия задач взяты с сайта acmp.ru