HDU 5627 Clarke and MST

問題描述

克拉克是一名人格分裂患者。某一天克拉克變成了一名圖論研究者。  
他學習了最小生成樹的幾個算法，于是突發奇想，想做一個位運算and的最大生成樹。  
一棵生成樹是由n-1n−1條邊組成的，且nn個點兩兩可達。一棵生成樹的大小等于所有在生成樹上的邊的權值經過位運算and後得到的數。  
現在他想找出最大的生成樹。      

輸入描述

第一行是一個整數T(1 \le T \le 5)T(1≤T≤5)，表示資料組數。  
每組資料第一行是兩個整數n, m(1 \le n, m \le 300000)n,m(1≤n,m≤300000)，分别表示點個數和邊個數。其中n, m > 100000n,m>100000的資料最多一組。  
接下來mm行，每行33個整數x, y, w(1 \le x, y \le n, 0 \le w \le 10^9)x,y,w(1≤x,y≤n,0≤w≤109)，表示x, yx,y之間有一條大小為ww的邊。      

輸出描述

每組資料輸出一行一個數，表示答案。若不存在生成樹，輸出00。      

輸入樣例

1

4 5

1 2 5

1 3 3

1 4 2

2 3 1

3 4 7

輸出樣例

1

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 3e5 + 10;
const int mod = 1e9 + 7;
int T, n, m, fa[maxn], ans;

struct point
{
    int x, y, w;
    void read(){ scanf("%d%d%d", &x, &y, &w); }
    bool operator <(const point&a)const
    {
        return w > a.w;
    }
}a[maxn];

int get(int x)
{
    return fa[x] == x ? x : fa[x] = get(fa[x]);
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        cin >> n >> m;
        for (int i = 0; i < m; i++) a[i].read();
        sort(a, a + m);
        ans = 0;
        for (int i = 29; i >= 0; i--)
        {
            int cnt = n - 1;
            for (int j = 1; j <= n; j++) fa[j] = j;
            for (int j = 0; j < m&&cnt; j++)
            {
                if (a[j].w < (1 << i)) break;
                if (a[j].w & (1 << i))
                {
                    int fx = get(a[j].x), fy = get(a[j].y);
                    if (fx == fy) continue;
                    fa[fx] = fy;    cnt--;
                }
            }
            if (!cnt)
            {
                ans |= (1 << i);
                for (int j = 0; j < m; j++)
                {
                    if (a[j].w < (1 << i)) break;
                    if (a[j].w & (1 << i)) a[cnt++] = a[j];
                }
                m = cnt;
            }
        }
        printf("%d\n", ans);
    }    
    return 0;
}