优化以下代码#include<iostream> using namespace std; #include<algorithm> #define MAXSIZE 100 int father[MAXSIZE];//存放父亲节点 typedef struct Mgraph { int s[MAXSIZE][MAXSIZE]; int n;//节点数 }; struct graph { int a, b, c; }arr[MAXSIZE]; bool compare(graph x, graph y) {//对边按照权值从小到大排序 return x.c < y.c; } int Find(int x) {//找到一个节点的根节点,并将其下面的所有节点的father都改为根节点。 while (x != father[x]) { int temp = x; x = father[x]; father[temp] = x; } return x; } int main() { Mgraph p; int m; cin >> p.n >> m; for (int i = 0; i < m; i++) { cin >> arr[i].a >> arr[i].b >> arr[i].c;//a,b间,需要c天 } for (int i = 1; i < p.n + 1; i++)//初始化father数组,将每个节点的父亲节点设置为自己 father[i] = i; sort(arr, arr + m, compare);//对边按照权值从小到大排序 for (int i = 0; i < m; i++) { if (Find(arr[i].a) != Find(arr[i].b)) father[Find(arr[i].a)] = Find(arr[i].b);//遍历每条边,如果该边的两个节点不在同一个连通块中,则将它们连通,并将它们的父亲节点设置为同一个节点。 if (Find(1) == Find(p.n)) {//如果1号节点和n号节点在同一个连通块中,则输出当前边的权值,并结束程序 cout << arr[i].c << endl; break; } } }
时间: 2024-01-21 16:02:33 浏览: 71
这段代码是 Kruskal 算法的实现,用于解决最小生成树问题。优化的方向可以从以下几个方面考虑:
1. 可以使用并查集的路径压缩优化,将 Find 函数中的路径压缩操作加上,可以有效降低时间复杂度。
2. 可以使用快读和快输来优化输入输出,加快读入和输出的速度。
3. 可以使用堆优化的 Kruskal 算法,将边按照权值建立小根堆,每次取出堆顶的边进行处理,可以降低时间复杂度。
4. 可以使用邻接表存储图,减小程序所占用的空间。
下面是代码的优化版:
```c++
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define MAXSIZE 100010
struct Edge {
int u, v, w;
bool operator < (const Edge& e) const {
return w < e.w;
}
};
int father[MAXSIZE];
int n, m;
int find(int x) {
if (x != father[x]) {
father[x] = find(father[x]);
}
return father[x];
}
int main() {
scanf("%d%d", &n, &m);
vector<Edge> edges(m);
for (int i = 0; i < m; i++) {
scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);
}
sort(edges.begin(), edges.end());
for (int i = 1; i <= n; i++) {
father[i] = i;
}
int ans = 0;
for (int i = 0; i < m; i++) {
int fu = find(edges[i].u);
int fv = find(edges[i].v);
if (fu == fv) {
continue;
}
father[fu] = fv;
ans = edges[i].w;
if (find(1) == find(n)) {
break;
}
}
printf("%d\n", ans);
return 0;
}
```
阅读全文