Решение задачи №142 «Минимальный каркас» с ACMP





Решение задачи №142 «Минимальный каркас» с ACMP

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

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

Входные данные
В первой строке входного файла INPUT.TXT находятся числа N и M (1 ≤ N ≤ 100; 1 ≤ M ≤ 6000), где N - количество вершин в графе, а M - количество рёбер. В каждой из последующих M строк записано по тройке чисел A, B, C, где A и B - номера вершин, соединённых ребром, а C - вес ребра (натуральное число, не превышающее 30000).

Выходные данные
В выходной файл OUTPUT.TXT выведите одно число - искомый вес.

#include <iostream>
using namespace std;
int main(){
int n,m,i,j,k,c0,c1,d,p=0;
cin>>n>>m;
int r[m][3],c[n+1];
for(k=0; k<m; ++k)
cin>>r[k][0]>>r[k][1]>>r[k][2];
for(i=1; i<=n; ++i)c[i]=i;
for(i=0; i<n-1; ++i){
d=30001;
for(k=0; k<m; ++k)
if(c[r[k][0]]!=c[r[k][1]]&&r[k][2]<d){
d=r[k][2];j=k; }
p+=d;
c0=c[r[j][0]];
c1=c[r[j][1]];
for(j=1;j<=n; ++j)if(c[j]==c1)c[j]=c0;}
cout<<p;
return 0;}



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