最小生成树
prim
1.朴素
#include <iostream>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
int n;
int dis[MAXN];
int w[MAXN][MAXN];
bool vis[MAXN];
int prim ();
int main () {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> w[i][j];
int ans = prim ();
cout << ans;
return 0;
}
int prim () {
int res = 0;
for (int i = 1; i <= n; i++) dis[i] = INF; dis[1] = 0;
for (int i = 1; i <= n; i++) {
int _min = INF, index;
for (int j = 1; j <= n; j++) {
if (vis[j] == 1) continue;
if (dis[j] < _min) {
_min = dis[j];
index = j;
}
}
res += _min;
vis[index] = 1;
for (int j = 1; j <= n; j++) {
if (vis[j] == 1) continue;
if (w[index][j] < dis[j]) {
dis[j] = w[index][j];
}
}
}
return res;
}
2.优化
#include <queue>
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 505;
const int INF = 0x3f3f3f3f;
int n, m;
int dis[MAXN];
bool vis[MAXN];
struct node {
int v, val;
node () {}
node (int V, int VAL) {
v = V, val = VAL;
}
};
struct edge {
int now, val;
edge () {}
edge (int N, int V) {
now = N, val = V;
}
};
bool operator < (const edge &x, const edge &y) {
return x.val > y.val;
}
vector<node> g[MAXN];
int prim ();
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
g[u].push_back( node (v, val));
g[v].push_back( node (u, val));
}
int ans = prim ();
cout << ans;
return 0;
}
int prim () {
for (int i = 1; i <= n; i++) dis[i] = INF; dis[1] = 0;
int res = 0;
priority_queue<edge> p; p.push( edge (1, 0));
while (! p.empty()) {
edge tem = p.top(); p.pop();
int u = tem.now, size = g[u].size();
if (vis[u] == 1) continue; vis[u] = 1, res += dis[u];
for (int i = 0; i < size; i++) {
int v = g[u][i].v, w = g[u][i].val;
if (w < dis[v]) {
dis[v] = w;
p.push( edge (v, dis[v]));
}
}
}
return res;
}
kruskal
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 105;
const int MAXM = 205;
int n, m;
int fa[MAXN];
struct node {
int u, v, val;
node () {}
node (int U, int V, int VAL) {
u = U, v = V, val = VAL;
}
}g[MAXM];
int UnionSet (int, int);
int FindSet (int);
int kruskal ();
void MakeSet ();
bool cmp (node x, node y) {
return x.val < y.val;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, val;
cin >> u >> v >> val;
g[i] = node (u, v, val);
}
sort (g + 1, g + 1 + m, cmp);
int ans = kruskal ();
cout << ans;
return 0;
}
int UnionSet (int x, int y, int val) {
int u = FindSet (x), v = FindSet (y);
if (u == v) return 0;
fa[u] = v;
return val;
}
int FindSet (int x) {
if (fa[x] != x) {
fa[x] = FindSet(fa[x]);
}
return fa[x];
}
int kruskal () {
int res = 0;
MakeSet ();
for (int i = 1; i <= m; i++) {
int u = g[i].u, v = g[i].v, w = g[i].val;
res += UnionSet(u, v, w);
}
return res;
}
void MakeSet () {
for (int i = 1; i <= n; i++) fa[i] = i;
}
Processed:
0.029, SQL:
8
