链接:hdu5627
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 mlines followed, each line contains three integers x,y,w(1≤x,y≤n,0≤w≤109), denoting an 、
- edge between x,ywith 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 7Sample Output
1题解
- 按位与最大生成树,从最高位贪心到最低位,看该位和其他已经获得的位能否构成生成树
- 能构成就加上这一位,不然就扔掉
1 |
|