注意到原题的数据过小，暴力即可水过，我们考虑更优复杂度。

思路

原来的暴力我们是通过 dfs 找环。既然我们需要遍历所有的环，不妨换一个视角。

我们尝试先建立 dfs 树，所有的环就是若干个树边和若干非树边（无向图所以是反祖边，等价于前向边）。考虑回边大于

1

的环：它可以拆分成若干只有一个回边的环，其异或和等价于这些环的异或和。

所以我们只需要知道所有只有一个回边的环异或和是否为

0

就行了。考虑向 dfs 树加边，预处理点到根的异或和，加边时计算即可。

Code

CPP

#include<bits/stdc++.h>
namespace wsz_sp
{
    using namespace std;
    #define int long long
    #define F(i,x,y) for(i=x;i<=y;i++)
    #define rF(i,x,y) for(i=x;i>=y;i--)
    typedef pair<int,int> PII;
    void cout_better()
    {
        ios::sync_with_stdio(0);
        cin.tie();
        cout.tie();
        return;
    }
    const int N=100+5,MOD=1e9+7,LN=20;
}
using namespace wsz_sp;
int n,m,g[N][N],xr[N];
bool vis[N];
vector<PII> ute;
void dfs(int x,int f)
{
    int i;
    vis[x]=1;
    F(i,1,n) 
    {
        if(g[x][i]==-1||i==f) continue;
        if(vis[i]) ute.push_back({x,i});
        else dfs(i,x);
    }
    return;
}
void dsf(int x,int f)
{
    int i;
    F(i,1,n) 
    {
        if(g[x][i]==-1||i==f) continue;
        if(xr[i]==0)
        {
            xr[i]=xr[x]^g[i][x];
            dsf(i,x);   
        }
    }
    return;
}
void solve()
{
    cin>>n>>m;
    int i,j;
    ute.clear();
    F(i,1,n) F(j,1,n) g[i][j]=-1;
    F(i,1,n) vis[i]=0,xr[i]=0;
    F(i,1,m)
    {
        int u,v,w;
        cin>>u>>v>>w;
        g[u][v]=g[v][u]=w;
    }
    F(i,1,n)
    {
        if(!vis[i])
        {
            dfs(1,0);
            dsf(1,0);
        }
    }
    for(auto x:ute) if((xr[x.first]^xr[x.second]^g[x.first][x.second])!=0) {cout<<"No\n";return;}
    cout<<"Yes"<<'\n';
    return;
}
signed main()
{
    int T=1;
    cout_better();
    cin>>T;
    while(T--) solve();
}

题解：P3907 环的异或

文章操作

思路

Code

相关推荐

评论

题解：P3907 环的异或