题意：n个点，m条边，从中选n-1条边构成一棵生成树，生成树的总值为边权值相与所得结果
官方思路：按位贪心，然后判断该位为1的所有边是否能构成一棵生成树，具体的看代码吧
其实这个题目是bc#73 hdu 5631复杂版，不过 5631 Rikka with Graph 的坑点实在不忍让人吐槽，题目出成这样有意思吗
/************************************************************** Problem:hdu 5627 User: youmi Language: C++ Result: Accepted Time:234MS Memory:7800K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep0(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define rep_1(i,n) for(int i=n;i>=1;i--) #define rep_0(i,n) for(int i=n-1;i>=0;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 1<<30 #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n,m; const int maxn=300000+10; struct side { int u,v,w; void init(int _u,int _v,int _w) { u=_u,v=_v,w=_w; } }e[maxn]; int fa[maxn]; int ans; vector<int>vt[40];//10^9最多30位 void init() { ans=0; for(int i=0;i<31;i++) vt[i].clear(); } int get_f(int x) { while(x!=fa[x]) { fa[x]=get_f(fa[x]); x=fa[x]; } return x; } void Union(int u,int v) { int x=get_f(u); int y=get_f(v); if(x<y) fa[v]=x; else fa[u]=y; } void solve(int temp) { for(int i=1;i<=n;i++) fa[i]=i; for(int i=0;i<vt[temp].size();++i)//并查集，生成树 { Union(e[vt[temp][i]].u,e[vt[temp][i]].v); } for(int i=1;i<=n;i++)//将所有点的父亲统一 fa[i]=get_f(i); int f=fa[1]; int cnt=0; for(int i=1;i<=n;i++) { if(fa[i]==f) ++cnt; } if(cnt==n) ans+=(1<<temp); } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int T_T; scanf("%d",&T_T); for(int kase=1;kase<=T_T;kase++) { init(); sc2(n,m); int u,v,w,bit; rep0(i,m) { scanf("%d%d%d",&u,&v,&w); e[i].init(u,v,w); rep0(j,30) { bit=1<<j; if(e[i].w&bit)//将对应为位为1的所有边放在一个vector表中 { vt[j].push_back(i); } } } for(int i=30;i>=0;--i) { if(vt[i].size()>=n-1) solve(i);//对每一位都进行检查是否可以构成一棵树 } pt(ans); } }