题目连接：
Description
Clarke is a patient with multiple personality disorder. One day he turned into a learner of graph theory.
He learned some algorithms of minimum spanning tree. Then he had a good idea, he wanted to find the maximum spanning tree with bit operation AND. A spanning tree is composed by n−1 edges. Each two points of n points can reach each other. The size of a spanning tree is generated by bit operation AND with values of n−1 edges. Now he wants to figure out the maximum spanning tree.Input
The first line contains an integer T(1≤T≤5), the number of test cases.
For each test case, the first line contains two integers n,m(2≤n≤300000,1≤m≤300000), denoting the number of points and the number of edge respectively. Then m lines followed, each line contains three integers x,y,w(1≤x,y≤n,0≤w≤109), denoting an edge between x,y with value w. The number of test case with n,m>100000 will not exceed 1.Output
For each test case, print a line contained an integer represented the answer. If there is no any spanning tree, print 0.
Sample Input
1
4 5 1 2 5 1 3 3 1 4 2 2 3 1 3 4 7Sample Output
1
Hint
题意
让你求&意义下的最大生成树
题解：
贪心，我们从高位到低位贪心，如果含有这一位的边能够构成一棵树的话，我们就可以直接把其他不含有这一位的边全部去掉
然后重复这个行为
这个贪心显然正确啦，至于判断能否构成一颗树，就用并查集就好啦
代码
#include#include #include using namespace std;const int maxn = 3e5+6;int x[maxn],y[maxn];int w[maxn];int flag[maxn];int fa[maxn];int fi(int x){ return x == fa[x]?x:fa[x]=fi(fa[x]);}int uni(int x,int y){ int p = fi(x),q = fi(y); if(p != q) fa[p]=fa[q];}int main(){ int t;scanf("%d",&t); for(int cas=1;cas<=t;cas++) { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&x[i],&y[i],&w[i]); int ans = 0; for(int i=30;i>=0;i--) { for(int j=1;j<=n;j++) fa[j]=j; for(int j=1;j<=m;j++) { if(((w[j]&ans)==ans)&&(w[j]>>i&1)) flag[j]=1; else flag[j]=0; } for(int j=1;j<=m;j++) if(flag[j]) uni(x[j],y[j]); int p = fi(1); int f = 1; for(int j=1;j<=n;j++) if(fi(j)!=p) f = 0; if(f) ans|=(1<