遵义网站推广,意大利做包招工的网站,做网站什么东西需要费用,制作一个教育网站洛谷p1111链接 克鲁斯卡尔算法的思路就是由森林变成树的过程#xff0c;其中最主要的就是贪心和并查集的应用。 我们知道链接n个点需要n-1条边#xff0c;这就满足的最后生成的是一颗树#xff0c;而不是一个环。在这n-1条边的选择上我们又要尽可能的让边的权重小#xff0…洛谷p1111链接 克鲁斯卡尔算法的思路就是由森林变成树的过程其中最主要的就是贪心和并查集的应用。 我们知道链接n个点需要n-1条边这就满足的最后生成的是一颗树而不是一个环。在这n-1条边的选择上我们又要尽可能的让边的权重小于是我们不难想到先对边的权重进行升序排序。然后再去判断这条边的两个点在不在一颗树上如果不在就连接这两颗树。 如果在就舍弃这条边继续找下一条边当联通的边等于n-1时这就是我呢最终得到的最小生成树。也就是我们最后的答案。 下面时最后的代码
#includebits/stdc.h
using namespace std;
struct road {int begin,end,value;
}a[100010];
int n,m,f[1010];
bool cmp(road x,road y) {return x.value y.value;
}
void init() {for(int i 1; i n; i)f[i] i;
}
int find(int x) {//查找根节点这里不用递归防止递归深度过深超时 int fx x;while(fx ! f[fx])fx f[fx];while(f[x] ! fx) {x f[x];f[x] fx;}
}
int main() {cin n m;for(int i 0; i m; i)cin a[i].begin a[i].end a[i].value;init();//初始化并查集的根结点。 sort(a,a m,cmp);//排序让value权重最小的有限在前。int maxn 0,sum 0;//设置最大的权重的为0方便后面比对 ,同时当前变数设置为0 for(int i 0; i m; i) {int fbegin find(a[i].begin);int fend find(a[i].end);if(fbegin ! fend) {f[fend] fbegin;//连接两颗树sum;//边的树加一。maxn max(maxn, a[i].value);//找到在这棵树上的最大权重边。 }if(sum n - 1)//森林变成树提前break; break;}cout maxn endl;return 0;
}
