首页 > 代码库 > bzoj 2115: [Wc2011] Xor xor高斯消元

bzoj 2115: [Wc2011] Xor xor高斯消元

2024-08-02 05:36:52   220人阅读

2115: [Wc2011] Xor

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 797  Solved: 375
[Submit][Status]

Description

Input

第一行包含两个整数N和 M， 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包含一个整数，表示最大的XOR和（十进制结果） 。

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

6

HINT

 

Source

 

　　本题对于我来说难点在于如何枚举出所有的环，想了半天tarjan，结果发现只需要dfs一次就行了，仔细想一下，也没什么反例。

　　剩下就是xor高斯消元了，注意去重。

 

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<set>using namespace std;#define MAXN 51000#define MAXV 51000#define MAXL 1000000#define MAXE MAXV*4typedef long long qword;struct Edge{        int np;        qword val;        Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y,qword z){        E[++tope].np=y;        E[tope].val=z;        E[tope].next=V[x];        V[x]=&E[tope];}bool vis[MAXN];qword path_val[MAXN];qword vec[MAXL];int totv=0;set<qword> S;void dfs(int now,qword pv){        Edge *ne;        path_val[now]=pv;        vis[now]=true;        for (ne=V[now];ne;ne=ne->next)        {                if (vis[ne->np])                {                        if (S.find(path_val[ne->np] ^ path_val[now] ^ ne->val)==S.end())                        {                                vec[totv++]=path_val[ne->np] ^ path_val[now] ^ ne->val;                                S.insert(vec[totv-1]);                        }                }else                {                        dfs(ne->np,pv^(ne->val));                }        }}bool cmp_v(qword x,qword y){        return x>y;}int main(){        freopen("input.txt","r",stdin);        int n,m;        scanf("%d%d",&n,&m);        int i,j,k,x,y;        qword z;        for (i=0;i<m;i++)        {                scanf("%d%d%lld",&x,&y,&z);                addedge(x,y,z);                addedge(y,x,z);        }        dfs(1,0);        for (i=0;i<totv;i++)        {                sort(vec+i,vec+totv,cmp_v);                totv=unique(vec+i,vec+totv)-vec;                for (j=i+1;j<totv;j++)                        if ((vec[j]^vec[i])<vec[j])                                vec[j]^=vec[i];        }        z=path_val[n];        for (i=0;i<totv;i++)                if ((z^vec[i])>z)                        z^=vec[i];        printf("%lld\n",z);}

 

bzoj 2115: [Wc2011] Xor xor高斯消元


联系
我们