Module: 스패닝 트리: Kruskal의 알고리즘


Problem

1/4

Kruskal의 알고리즘: 시작

Theory Click to read/hide

지정된 에지 가중치가 있는 그래프의 최소 스패닝 트리 예: 


Kruskal의 알고리즘:

1) 가중치로 가장자리 정렬  감소하지 않는 순서로.
2) 우리는 n개의 트리 목록을 형성합니다(각 정점은 트리입니다).
3)  이러한 트리를 최소 스패닝 트리로 결합하는 프로세스를 시작합니다.
      모든 에지가 트래버스되고 현재 에지의 끝이 다른 하위 트리에 속하는 경우 이러한 하위 트리가 병합됩니다.
4) 모든 가장자리의 열거가 끝나면 모든 정점이 동일한 하위 트리에 속합니다.

Problem

<사업부> 연결된 그래프에서 최소 가중치 스패닝 트리를 찾는 데 필요합니다.
<사업부>  
<사업부> 입력 데이터 형식:
<사업부>  
<사업부> 입력 파일의 첫 번째 줄에는 두 개의 자연수 N, M이 포함되어 있습니다. 각각 그래프의 꼭지점 수와 가장자리 수입니다. 다음 m 줄에는 한 줄에 하나씩 가장자리에 대한 설명이 포함됩니다. 에지 번호 i는 각각 에지의 끝점과 가중치( 1 <= B< sub>i, Ei <= N, 0 <= Wi <= 232< /sup>-1.N <= 10, M <= 10).
<사업부>  
<사업부> 출력 형식:
<사업부>  
<사업부> 출력 파일의 유일한 줄에는 하나의 자연수(최소 스패닝 트리의 가중치)가 포함되어야 합니다. 
<사업부>  
<사업부> <몸>

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
엔터 출력
<사업부> 4 4 <사업부> 1 2 1 <사업부> 2 3 2 <사업부> 3 4 5 <사업부> 4 1 4 7
Write the program below 
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge
{
	int l,a,b;
};

bool cmp(const edge &a, const edge &b)
{
    return a.l < b.l;
}

int main()
{
	int m, n;
	cin >> n >> m;

	vector < edge > g(m);

	for (int i = 0; i < m; i++)
	{
		int a, b, l;
		cin >> a >> b >>l;
		edge e;
                e.l = l; e.a= a-1; e.b = b-1;
		g[i] = e;
	}
	long long cost = 0;
	vector < pair<int, int> > res;

	sort(g.begin(), g.end(),cmp);
	vector<int> tree_id(n);
	for (int i = 0; i < n; ++i)
		tree_id[i] = i;
	for (int i = 0; i < m; ++i)
	{
		int a = g[i].a, b = g[i].b, l = g[i].l;
		if (tree_id[a] != tree_id[b])
		{        
			res.push_back(make_pair(a, b));
			int old_id = tree_id[b], new_id = tree_id[a];
			for (int j = 0; j < n; ++j)
				if (tree_id[j] == old_id)
					tree_id[j] = new_id;
		}
	}

	cout << cost;
	return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!