网站建设论文题目,做ppt的素材网站,系统安装两个wordpress,wordpress 文章要想去除边#xff0c;并且不改变连通性#xff0c;而且去除的值最大#xff0c;相当于保留最小生成树。 注意这题连通块有若干个#xff0c;所以运行Kruskal相当于形成若干个最小生成树。 如果是prim只能事先处理好各个连通块#xff0c;然后在连通块内部单独用prim
题目… 要想去除边并且不改变连通性而且去除的值最大相当于保留最小生成树。 注意这题连通块有若干个所以运行Kruskal相当于形成若干个最小生成树。 如果是prim只能事先处理好各个连通块然后在连通块内部单独用prim
题目链接
#include iostream
#include cstring
#include algorithmusing namespace std;
const int N 110;
const int M 10010;struct Edge {int a, b, w;bool operator (const Edge t) const {return w t.w;}
};Edge e[M];
int p[N];
int n, m;int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}
int kruskal() {for (int i 1; i n; i ) p[i] i;sort(e, e m);int res 0;for (int i 0; i m; i ) {int a find(e[i].a);int b find(e[i].b);if (a ! b) {p[a] b;}else {res e[i].w;}}return res;
}
int main() {scanf(%d%d, n, m);int a, b, w;for (int i 0; i m; i ) {scanf(%d%d%d, a, b, w);e[i] {a, b, w};}cout kruskal() endl;
}
