即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

hdu 5544 Ba Gua Zhen(线性基+dfs)

编程语言 johsnows 23℃ 0评论

题意:

一个无向图,每条边有值,找出无向图中所有的环的异或和,问这些值能异或出来的最大值。


解题思路:

去年的做的比赛里的题,今年才补上。

找环用dfs跑一遍图就可以找出来了,然后求最大的异或和,这是线性基的应用,用高消对求出来的异或和跑一下求出线性基,然后就是线性基求异或最大值的套路了。

思路是蛮清晰但是还是很容易错,用来存环的异或和的数组和边数m开的一样大了结果超了,但是hdu返回tle,抠了好久的时间也不对,去uestc上交了一发是re才察觉到这里出了问题,然后细节也要处理好,比如存边和线性基的数组都要开longlong


代码:

#include 
#define ps push_back
#define LL long long 
using namespace std;
const int maxn=1e5+5;
long long  a[maxn*100];
int book[maxn];
long long xo[maxn];
vector >edg[maxn];
int  n, top;
void dfs(int x, int y)
{
    book[x]=1;
    int i, j, to;
    for(i=0; i<(int)edg[x].size(); i++)
    {
        to=edg[x][i].first;
        if(to==y)continue;
        if(book[to])
        {
            a[top++]=xo[x]^xo[to]^edg[x][i].second;
        }
        else if(book[to]==0)
        {
            xo[to]=xo[x]^edg[x][i].second; 
            dfs(to, x);
        }
    }
    return;
}
void gauss()  
{  
    int i, j, row=1;  
    for(j=60; j>=0; j--)  
    {  
        for(i=row; i<=top-1; i++)  
        {  
            if((a[i]>>j)&1)  
            {  
                break;  
            }  
        }  
            if(i>top-1)continue;  
            swap(a[i], a[row]);  
            for(i=0; i>j)&1) a[i]^=a[row];  
            }  
            row++;  
    }  
}
int main()
{
    int x, y, m, i, j, e=1, t;
    long long z;
    long long ans=0;
    scanf("%d", &t);
    while(t--)
    {
        top=0;
        scanf("%d%d", &n, &m);
        for(i=1; i<=60; i++)a[i]=0;
        for(i=1; i<=m; i++)
        {
            scanf("%d%d%lld", &x, &y, &z);
            edg[x].ps(make_pair(y,z));
            edg[y].ps(make_pair(x,z));
        }
        for(i=1; i<=n; i++)
        if(book[i]==0)dfs(i, -1);
        for(i=top; i<=60; i++)a[i]=0;
        gauss();
        ans=0;
        for(i=0; i<=60; i++)
        {
             ans=max(ans, ans^a[i]);
        }
        printf("Case #%d: %lld\n", e++, ans);
        for(i=1; i<=n; i++){book[i]=xo[i]=0;edg[i].clear();}
    }
}





转载请注明:CodingBlog » hdu 5544 Ba Gua Zhen(线性基+dfs)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情