Clarke and MST

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 708 Accepted Submission(s): 408

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

Source
BestCoder Round #72 (div.2)

题目大意：求最大与生成树。

思路应该挺简单的，就是怎么简单的去实现。我们从每一位开始考虑：这一位有1的能否组成一颗生成树，因为我们是从最高位去看，所以若能组成，必然最优，否则继续往地位寻找。

若能组成，则把这一位二进制没有1的边全部删掉，也就是标记一下，以后不用即可。然后用这里面的边再去看下一位。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=3e5+10;
int T,n,m,f[N],res,vis[N],cnt;
struct node{
	int u,v,w;
}t[N];
vector<int> v[32];
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int mst(int k){
	for(int i=1;i<=n;i++)	f[i]=i;	int cnt=0;
	for(int i=0;i<v[k].size();i++){
		if(vis[v[k][i]])	continue;
		int fa=find(t[v[k][i]].u);	int fb=find(t[v[k][i]].v);
		if(fa!=fb)	cnt++,f[fa]=fb;
		if(cnt==n-1)	return 1;
	}
	return cnt==n-1;
}
signed main(){
	cin>>T;
	while(T--){
		scanf("%d %d",&n,&m); res=0;
		for(int i=1;i<=m;i++){
			scanf("%d %d %d",&t[i].u,&t[i].v,&t[i].w);
			for(int j=30;j>=0;j--)	if((t[i].w>>j)&1)	v[j].push_back(i);
		}
		for(int i=30;i>=0;i--){
			if(mst(i)){
				res|=(1<<i);
				for(int i=1;i<=m;i++)	if(t[i].w&(1<<i)==0)	vis[i]=1;
			}
		}
		printf("%d\n",res);
	}
	return 0;
}