Problem 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 7
Sample Output 1
大致题意：给你n个点m条边以及m条边的权值，让你构造一棵生成树，使得生成树的权值and和最大。
思路：（借用袁神的思路）首先我们得分析位运算与的特征，很明显，与运算和运算顺序没有关系，不像异或（那样这题就没得做了），那么要求一个生成树的与结果最大，就是所有边权在二进制相应位下都为1，那么就按位来一个枚举，从最大位开始，依次枚举2的倍数tmp，只有和tmp的与运算等于tmp的边权才是合法边，再验证是否能在合法边中找到生成树，如果能，就将这个tmp记录下来成为now，之后的tmp都要或（位运算）上这个now，最后枚举到1结束，输出当前now。 验证是否能够找到生成树就直接用并查集
代码如下
#include<iostream> #include<algorithm> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<cstring> using namespace std; const int maxn=300005; struct node { int x,y,w; }edge[maxn]; int pre[maxn]; int n,m; int find(int x) { int r=x; while (pre[r]!=r) r=pre[r]; int i=x; int j; while(i!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } //void join(int x,int y) //{ // int f1=find(x); // int f2=find(y); // if(f1!=f2) // { // pre[f2]=f1; // } //} int main() { int T,temp; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w); int now=0; for(int k=30;k>=0;k--) { temp=now|(1<<k);//假设第k位置上能为1（即所选的边第k位置上都为1，且能构成树），那么所能得到的最大值可能为now|(1<<k) //接下来验证，如果可以，则将temp赋给now for(int i=1;i<=n;i++) pre[i]=i; for(int i=1;i<=m;i++) { if((temp&edge[i].w)==temp)//表示该边可以选择，加入集合 { int f1=find(edge[i].x); int f2=find(edge[i].y); if(f1!=f2) { pre[f1]=f2; } } } int sum=0; //判断选择的边是否能构成树 for(int i=1;i<=n;i++) if(pre[i]==i) sum++; if(sum==1)//如果能 now=temp; } printf("%d\n",now); } return 0; }