Scribd
Upload
2 views3 pages

Include

The document contains a C++ implementation of Prim's algorithm for finding the Minimum Spanning Tree (MST) of a graph. It reads an adjacency matrix from an input file, computes the MST starting from a specified node, and outputs the total weight and edges of the MST. If the graph is not connected, it outputs 0.

Uploaded by

leminh20041911
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Include

The document contains a C++ implementation of Prim's algorithm for finding the Minimum Spanning Tree (MST) of a graph. It reads an adjacency matrix from an input file, computes the MST starting from a specified node, and outputs the total weight and edges of the MST. If the graph is not connected, it outputs 0.

Uploaded by

leminh20041911
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

#include <bits/stdc++.

h>
using namespace std;

const int MAXN = 105;


const int INF = 1e9;

int n, s;
int a[MAXN][MAXN];
bool visited[MAXN];
int dist[MAXN];
int parent[MAXN];

int main() {
freopen("[Link]", "r", stdin);
freopen("[Link]", "w", stdout);

cin >> n >> s;

for (int i = 1; i <= n; i++) {


for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}

for (int i = 1; i <= n; i++) {


dist[i] = INF;
visited[i] = false;
parent[i] = -1;
}

dist[s] = 0;

int totalWeight = 0;
vector<tuple<int,int,int>> mst;

for (int i = 1; i <= n; i++) {


int u = -1;
int minDist = INF;

for (int j = 1; j <= n; j++) {


if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}

if (u == -1) break; // không liên thông

visited[u] = true;
totalWeight += dist[u];

if (parent[u] != -1) {
mst.push_back({parent[u], u, dist[u]});
}

for (int v = 1; v <= n; v++) {


if (!visited[v] && a[u][v] < dist[v]) {
dist[v] = a[u][v];
parent[v] = u;
}
}
}

if ([Link]() != n - 1) {
cout << 0;
return 0;
}

cout << totalWeight << endl;


for (auto [u, v, w] : mst) {
cout << u << " " << v << " " << w << endl;
}

return 0;
}#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;


const int INF = 1e9;

int n, s;
int a[MAXN][MAXN];
bool visited[MAXN];
int dist[MAXN];
int parent[MAXN];

int main() {
freopen("[Link]", "r", stdin);
freopen("[Link]", "w", stdout);

cin >> n >> s;

for (int i = 1; i <= n; i++) {


for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}

for (int i = 1; i <= n; i++) {


dist[i] = INF;
visited[i] = false;
parent[i] = -1;
}

dist[s] = 0;

int totalWeight = 0;
vector<tuple<int,int,int>> mst;

for (int i = 1; i <= n; i++) {


int u = -1;
int minDist = INF;

for (int j = 1; j <= n; j++) {


if (!visited[j] && dist[j] < minDist) {
minDist = dist[j];
u = j;
}
}

if (u == -1) break;

visited[u] = true;
totalWeight += dist[u];

if (parent[u] != -1) {
mst.push_back({parent[u], u, dist[u]});
}

for (int v = 1; v <= n; v++) {


if (!visited[v] && a[u][v] < dist[v]) {
dist[v] = a[u][v];
parent[v] = u;
}
}
}

if ([Link]() != n - 1) {
cout << 0;
return 0;
}

cout << totalWeight << endl;


for (auto [u, v, w] : mst) {
cout << u << " " << v << " " << w << endl;
}

return 0;
}

You might also like