本文主要是介绍Clarke and MST（最大生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
克拉克是一名人格分裂患者。某一天克拉克变成了一名图论研究者。 他学习了最小生成树的几个算法，于是突发奇想，想做一个位运算and的最大生成树。 一棵生成树是由n-1n−1条边组成的，且nn个点两两可达。一棵生成树的大小等于所有在生成树上的边的权值经过位运算and后得到的数。 现在他想找出最大的生成树。 输入描述 第一行是一个整数T(1 \le T \le 5)T(1≤T≤5)，表示数据组数。 每组数据第一行是两个整数n, m(1 \le n, m \le 300000)n,m(1≤n,m≤300000)，分别表示点个数和边个数。其中n, m > 100000n,m>100000的数据最多一组。 接下来mm行，每行33个整数x, y, w(1 \le x, y \le n, 0 \le w \le 10^9)x,y,w(1≤x,y≤n,0≤w≤10 9 )，表示x, yx,y之间有一条大小为ww的边。 输出描述 每组数据输出一行一个数，表示答案。若不存在生成树，输出00。 输入样例 1 4 5 1 2 5 1 3 3 1 4 2 2 3 1 3 4 7 输出样例 1
最大生成树，只不过答案是用&计算。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node {int x,y,c; } std1[300006]; int f[300006]; bool cmp(node n,node m) {return n.c>m.c; } int find(int r) {if(r==f[r]){return r;}else{f[r]=find(f[r]);return f[r];} } int merge(node n) {int xx=find(n.x);int yy=find(n.y);if(xx!=yy){f[yy]=xx;return 1;}return 0; } int main() {int t,n,m,j,k,i;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);for(i=1; i<=n; i++){f[i]=i;}for(i=1; i<=m; i++){scanf("%d %d %d",&std1[i].x,&std1[i].y,&std1[i].c);}sort(std1+1,std1+m+1,cmp);int f=0;int cont=0;int sum;int k=1;for(i=1; i<=m; i++){if(merge(std1[i])==1){if(k==1){k=0;merge(std1[i]);sum=std1[i].c;}else if(k==0){sum&=std1[i].c;merge(std1[i]);}cont++;}if(cont==n-1){f=1;}}if(f==0){printf("0\n");}else{printf("%d\n",sum);}}return 0; }
这篇关于Clarke and MST（最大生成树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
