HDU 5627 Clarke and MST - dblank

HDU 5627 Clarke and MST

思路:从高位贪心到低位,用位运算判断该位和其他已经获得的位为1的边能否构成生成树。
#include<iostream>  
#include<cstdio>  
#include<algorithm>  
#include<map>  
#include<cstring>  
#include<map>  
#include<set>  
#include<queue>  
#include<stack>  
#include<cmath>  
using namespace std;  
const double eps = 1e-10;  
const int inf = 0x7fffffff, N = 3e5 + 10;  
typedef long long ll;  
using namespace std;  
int root[N], v[N],n, m,xx[N], yy[N];  
int Find(int x)  
{  
    return x == root[x] ? x: root[x] = Find(root[x]);  
}  
int join(int x, int y)  
{  
    int a = Find(x), b = Find(y);  
    if(a!=b)  
    {  
        root[a] = b;  
        return 1;  
    }  
    return 0;  
}  
int main()  
{  
    int t;  
    cin>>t;  
    while(t--)  
    {  
        scanf("%d%d", &n, &m);  
        for(int i = 1; i<=m; i++) scanf("%d%d%d",&xx[i], &yy[i], &v[i]);  
        int ans = 0;  
        for(int i = 30; i>=0; i--)  
        {  
            int bit = 1<<i, sum = 0;  
            ans |= bit;//先将加入到答案  
            for(int j = 1; j<=n; j++) root[j] = j;//每次都必须初始化,因为每次都可以改变生成树。  
            for(int j = 1; j<=m; j++)  
            {  
                if((v[j] & ans) == ans)//判断已经获得位和该位是否都为1,题目数据有点弱感觉,我这里v[j] & bit) == bit这样写都ac了  
                {  
                    if(join(xx[j], yy[j]))  
                        sum ++;  
                }  
            }  
            if(sum != n-1)  
                ans ^= bit;  
        }  
        cout<<ans<<endl;  
    }  
    return 0;  
}

 

发表新评论