题解：AT_abc396_e [ABC396E] Min of Restricted Sum

wuzebang2009 · 2025-03-13 09:59:48 · 题解

AT_abc396_e [ABC396E] Min of Restricted Sum

我们在点 A_{X_i} 和 A_{Y_i} 建一条边权为 Z_i 的边，A_{Y_i}=A_{X_i} \oplus Z_i ，我们知道在一个联通块中确定一个点的值所有点的值都是确定的，那么如果其中有冲突，那么就直接输出 -1，否则我们知道变动联通块的第一个值在二进制下某一为的值，所有的的其他在联通快中的值都会翻转，那么如果这一位为 1 的点超过半数那么可以翻转，这样可以使最终值最小。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m,ans[N];
int h[N],nxt[N<<1],ver[N<<1],edge[N<<1],tot=0;
bool vis[N];
vector<int> path;

void add(int a,int b,int c){
    ver[++tot]=b,edge[tot]=c,nxt[tot]=h[a],h[a]=tot;
}

void dfs(int x,int val){
    if(vis[x]){
        if(ans[x]!=val) {cout<<-1;exit(0);}
        return;
    }
    ans[x]=val,vis[x]=1,path.push_back(x);
    for(int i=h[x];i;i=nxt[i]){
        int v=ver[i],e=edge[i];
        dfs(v,val^e);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i,0);
            for(int j=0;j<=30;j++){
                int cnt=0;
                for(int x=0;x<path.size();x++){
                    if(ans[path[x]]&(1<<j)) cnt++;
                }
                if(cnt*2>path.size()){
                    for(int x=0;x<path.size();x++){
                        ans[path[x]]^=(1<<j);
                    }
                }
            }
            path.clear();
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }

    return 0;
}