Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- #define NMAX 103
- struct {
- int x, y;
- float cost;
- } edge[NMAX];
- int n, m, subArbOf[NMAX * NMAX];
- float sum;
- void read() {
- cin >> n >> m;
- for (int i = 1; i <= m; i++) {
- cin >> edge[i].x >> edge[i].y >> edge[i].cost;
- }
- }
- void bubbleSort() {
- bool sorted = false;
- while (!sorted) {
- sorted = true;
- for (int i = 1; i < m; i++) {
- if (edge[i].cost > edge[i + 1].cost) {
- swap(edge[i], edge[i + 1]);
- sorted = false;
- }
- }
- }
- }
- void kruskal() {
- for (int i = 1; i <= n; i++) {
- subArbOf[i] = i;
- }
- for (int i = 1; i <= m; i++) {
- if (subArbOf[edge[i].x] != subArbOf[edge[i].y]) {
- sum += edge[i].cost;
- int subArbOfX = subArbOf[edge[i].x],
- subArbOfY = subArbOf[edge[i].y];
- for (int j = 1; j <= n; j++) {
- if (subArbOf[j] == subArbOfY) {
- subArbOf[j] = subArbOfX;
- }
- }
- }
- }
- }
- int main() {
- read();
- bubbleSort();
- kruskal();
- cout << sum << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment