算法标签:==贪心== ==图论==
Kruskal 算法思路
这个算法主要是运用了贪心思想。
首先对每个边进行排序,每次选取最小的边,用并查集判断是否选过或形成环。
当边选够了,输出。
注意事项
结束循环的条件有两种:
++ cnt >= n - 1
:这时候注意sum += edge[i].value
在判断的前面,因为判断的意义是:到现在为止,我又没有选够。++ cnt >= n
:这时候sum += edge[i].value
在判断的后面,因为判断的意义是:如果选了这个,有没有超。
代码
#include <bits/stdc++.h>
using namespace std;
int f[1000005], n, m, cnt, sum;
struct G{
int f, t, v;
} e[10000005];
bool cmp(G x, G y) {
return x.v < y.v;
}
int find(int i) {
if (f[i] == i) return i;
else return f[i] = find(f[i]);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i ++) {
f[i] = i;
}
for (int i = 1; i <= m; i ++) {
int x, y, z; cin >> x >> y >> z;
e[i].f = x;
e[i].t = y;
e[i].v = z;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= m; i ++) {
// cout << e[i].f << " " << e[i].t << " " << e[i].v << "\n";
}
for (int i = 1; i <= m; i ++) {
int x, y;
x = e[i].f;
y = e[i].t;
x = find(x);
y = find(y);
if (x == y) continue;
f[x] = y;
if (++ cnt >= n) break;
sum += e[i].v;
}
if (cnt < n - 1) cout << "orz";
else cout << sum;
return 0;
}
Prim 算法思路
定义 dis[i]
为:生成完的点到所有点的最小距离。每次有新的节点生成完后更新一下就行。
每次找边权最短的比连接的那个点生成就行了。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m, dis[1000005], a[105][105];
int main() {
memset(dis, 0x7f, sizeof(dis));
memset(a, 0x7f, sizeof(a));
cin >> n >> m;
for (int i = 1; i <= n; i ++)
a[i][i] = 0;
for (int i = 1; i <= m; i ++) {
int x, y, z;
cin >> x >> y >> z;
a[x][y] = z;
a[y][x] = z;
}
for (int i = 1; i <= n; i ++)
dis[i] = a[1][i];
int cnt = 1, sum = 0;
int nw = 1;
// for (int i = 1; i <= n; i ++) {
// for (int j = 1; j <= n; j ++) {
// printf("%10d ", a[i][j]);
// }
//
// cout << "\n";
// }
while (cnt < n) {
int flag = 0;
int minn = 1e9;
for (int i = 1; i <= n; i ++) {
if (dis[i] > 0) {
if (minn > dis[i]) {
minn = dis[i];
flag = i;
}
}
}
// cout << flag << " " << minn << " " << nw << "\n";
sum += minn;
nw = flag;
for (int i = 1; i <= n; i ++)
dis[i] = min(dis[i], a[nw][i]);
cnt ++;
}
cout << sum;
}