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
4 5
1 2 5
1 3 3
1 4 2
2 3 1
3 4 7
Sample Output
1
Source
首先贴上自己的写法，虽然不是很正宗的做法
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 300006
#define M 300006
#define inf 1e12
struct Node{
int x,y;
int cost;
}edge[M];
int n,m;
int fa[N];
void init(){
for(int i=;i<N;i++){
fa[i]=i;
}
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool cmp(Node a,Node b){
return a.cost>b.cost;
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
init();
for(int i=;i<m;i++){
int a,b,c;
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].cost);
}
sort(edge,edge+m,cmp);
int flag=;
int ans;
int num=n-;
for(int i=;i<m;i++){
int root1=find(edge[i].x);
int root2=find(edge[i].y);
if(root1!=root2){
if(flag){
ans=edge[i].cost;
flag=;
}else{
ans&=edge[i].cost;
}
fa[root1]=root2;
num--;
}
}
if(num!=){
printf("0\n");
}
else{
printf("%d\n",ans);
}
} return ;
}
官方题解：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = + ; struct Edge{
int from,to,dis;
}a[N],b[N];
int fa[N];
int find(int x){
if(x==fa[x]) return x;
return fa[x] = find(fa[x]);
}
int tmp;
bool solve(int pos, Edge *a, int n, int m){
for(int i=;i<=n;++i)
fa[i] = i;
int cnt = ;
tmp = ;
for(int i=;i<=m;++i){
if(((a[i].dis>>pos)&)==)
continue; int fu = find(a[i].from);
int fv = find(a[i].to);
if(fu!=fv){
if(cnt==)
tmp = a[i].dis;
else
tmp &= a[i].dis; fa[fu] = fv;
cnt++;
if(cnt==n-)
return true;
}
}
return false;
}
int main() { int t,n,m;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m); for(int i=;i<=m;++i){
scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].dis);
}
int ans = ;
for(int i=;i>=;--i){
if(solve(i,a,n,m)){
ans = tmp;
int mm = ;
for(int i=;i<=m;++i){
if((a[i].dis>>i)&)
b[++mm] = a[i];
}
m = mm;
for(int i=;i<=m;++i)
a[i] = b[i];
}
}
cout<<ans<<endl;
}
return ;
}