http://www.cnblogs.com/wenruo/p/5188495.html
克拉克是一名人格分裂患者。某一天克拉克变成了一名图论研究者。
他学习了最小生成树的几个算法，于是突发奇想，想做一个位运算and的最大生成树。
一棵生成树是由n−1条边组成的，且n个点两两可达。一棵生成树的大小等于所有在生成树上的边的权值经过位运算and后得到的数。
现在他想找出最大的生成树。
第一行是一个整数T(1≤T≤5)，表示数据组数。
每组数据第一行是两个整数n,m(1≤n,m≤300000)，分别表示点个数和边个数。其中n,m>100000n, 的数据最多一组。
接下来m行，每行3个整数x,y,w(1≤x,y≤n,0≤w≤109)9??)，表示x,yx, yx,y之间有一条大小为www的边。
每组数据输出一行一个数，表示答案。若不存在生成树，输出000。
1 4 5 1 2 5 1 3 3 1 4 2 2 3 1 3 4 7
1
题解：
我们贪心的从大到小枚举每一个位，如果一个位能取当且仅当所有权值这个位不为0的边能形成一棵生成树。是否能形成生成树我们简单的bfs一下就行了。
代码：
#include <bits/stdc++.h>
#define clr(x,c) memset(x,c,sizeof(x))
using namespace std;
int Scan() {
int res = 0, flag = 0;
char ch;
if((ch = getchar()) == ‘-‘) flag = 1;
else if(ch >= ‘0‘ && ch <= ‘9‘) res = ch - ‘0‘;
while((ch = getchar()) >= ‘0‘ && ch <= ‘9‘)
res = res * 10 + (ch - ‘0‘);
return flag ? -res : res;
}
const int N = 300005;
struct Edge {
int to;
int w;
Edge(int to = 0, int w = 0) : to(to), w(w){}
} edge[N];
vector<Edge> G[N];
bool vis[N];
int n, m;
int now;
bool bfs()
{
queue<int> q;
clr(vis, false);
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (unsigned i = 0; i < G[u].size(); ++i) {
int v = G[u][i].to;
int w = G[u][i].w;
if (!vis[v] && (w & now) == now) {
vis[v] = true;
q.push(v);
}
}
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) return false;
}
return true;
}
int main()
{
int t = Scan();
while (t--) {
n = Scan(); m = Scan();
for (int i = 1; i <= n; ++i)
G[i].clear();
int x, y, w;
for (int i = 0; i < m; ++i) {
x = Scan(); y = Scan(); w = Scan();
G[x].push_back(Edge(y, w));
G[y].push_back(Edge(x, w));
}
int ans = 0;
for (int i = 30; i >= 0; --i) {
now = ((1 << i) | ans);
if (bfs()) ans = now;
}
printf("%d\n", ans);
}
return 0;
}
开始用链式前向星一直T啊，555~是我写挫了还是链式前向星本身比较慢………
HDU5627--Clarke and MST （bfs+位运算）
原文：http://www.cnblogs.com/wenruo/p/5188495.html