这题对我来说有一点点点点点....难!看题解都理解了好久。
题目大意:
给一个n个点m条边的无向图,有些边上已经标记了边权0或者1,现在要给剩下的边标记0或1,使得图中任意的环上的边异或和为0。问一共有几种标记方案。
思路:
本题有一个很巧妙的转化,就是把边权转为点权。对于一条边w(u,v),我们将边权转移到两个端点上,赋予u和v分别为各自点权au和av,那么我们令边权=au^av。
显然,在环上每个点有2条边,那么求环上的边权异或就是求每个点异或2次的异或和。也就是,每个点权会参与2次异或。那么我们可以得到,环上的异或和一定为0。而不构成环的点随便选,因此每个点选0/1,一共n个点的连通块,一共会有方案数2^n种。
但是对于一条边w(u,v)来说,(au=0)^(av=1)与(au=1)^(av=0)是相同的,(au=0)^(av=0)与(au=1)^(av=1)也是相同的。因为我们实际上选择的是边权方案,所以按照点权方案算是重复的,实际上只有总方案数的一半。
即真正的方案数为2^(n-1)种。
本题的一个难点在于,有些边是确定的有些边不确定。如果我们仅考虑确定的边,我们选择其中一个点赋0/1,那么该点所在连通块中剩下的点权我们也可以确定下来。那么我们可以先把确定的边建图,然后我们可以利用dfs去遍历连通块上的点一一确定,注意如果连通块上有环的话,一定会有一个点被访问第2次,此时我们需要判断这个点此时计算的点权和之前已经计算过的点权有没有矛盾,如果矛盾了说明环上为0已经不可能,我们直接提前输出0然后结束程序就可以了。那么对于一个独立且没有矛盾的连通块来说,方案数是2种。
接着我们考虑不确定的边。这里有两种情况:
(一)枚举的边上两点已经在同一个连通块内。如果是这种情况的话,这条边一定是构成环的最后一条边。那么这两个点实际上点权已经确定下来了,对答案没有影响。
(二)枚举的边上两点不在同一个连通块。此时这条边是不会影响环的,选0/1都没问题,因此对答案贡献是*2。但是这条边会不会后面变成环的一条边呢?答案是可能的,但是依然不影响这条边可以选0/1.
因此最后的答案就是,每连通两个不同的连通块答案乘2。
代码:
#include<bits/stdc++.h> using namespace std; const long long mod=998244353; int n,m,fa[100050],cnt,a[100050],flag=0,vis[100050]; long long ans=1; struct node{ int to,next,w; }p[200030]; struct Node{ int u,v,w; }e[100005]; bool cmp(Node a,Node b){ return a.w>b.w; } int tot,head[100050]; void add(int a,int b,int c){ p[tot].to=b; p[tot].next=head[a]; p[tot].w=c; head[a]=tot++; } int find(int x){ if(x!=fa[x])return fa[x]=find(fa[x]); return fa[x]; } void join(int a,int b){ int fx,fy; fx=find(a);fy=find(b); fa[fx]=fy; } void init() { tot=0; memset(vis,0,sizeof(vis)); memset(head,-1,sizeof(head)); for(int i=0;i<100001;i++)fa[i]=i; } void dfs(int x){ vis[x]=1; if(flag)return; for(int i=head[x];~i;i=p[i].next){ int y=p[i].to; if(vis[y]){ if(a[y]!=p[i].w^a[x]){ flag=1;return; } } else { a[y]=p[i].w^a[x]; dfs(y); } } } int main() { cin>>n>>m; init(); for(int i=1;i<=m;i++){ int u,v,w; cin>>u>>v>>w; e[i].u=u;e[i].v=v;e[i].w=w; } sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++){ if(e[i].w!=-1){ add(e[i].u,e[i].v,e[i].w); add(e[i].v,e[i].u,e[i].w); join(e[i].u,e[i].v); } else { break; } } for(int i=1;i<=n;i++){ if(vis[i]==0){ dfs(i); } } if(flag){ cout<<0<<endl; return 0; } for(int i=m;i>=1;i--){ if(e[i].w==-1){ int fx,fy; fx=find(e[i].u);fy=find(e[i].v); if(fx!=fy)ans=ans*2%mod; join(fx,fy); } else { break; } } cout<<ans%mod<<endl; return 0; }