题解：AT_abc396_e [ABC396E] Min of Restricted Sum

· · 题解

原题传送门

挺有意思的一道题

把每个限制看成一条从 x_i 到 y_i 的无向边。

这样 n 个点会被分成若干个联通块，考虑对于一个块内求解。

显然结论：在一个块内，只要确定了其中一个数，别的也都唯一确定。

重要结论：对于一个存在解的块，随意确定其中一个数，仍然存在解。 因为只有环才会影响解的有无性，可以自己画几个环理解一下。

这样，我们就可以对每一个二进制位分别讨论。每条边边权只有 0 或 1，表示边两端当前二进制位一样或不一样。

把原图删减一些边，变成森林，对于每棵树做树型 dp，f_{i,{0/1}} 表示这个点填 0/1 时其子树的贡献。再为我们钦定的树根选择 0 或 1，其他也就唯一确定。

然而一天后发现其实选一个点01各试一下取较优就行。

最后遍历所有边判断解的合法性即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200100;
int n,m,x[N],y[N],z[N];
int ans[N];
struct edge{
    int nxt,to,w;
}e[N*2];
int cnt,head[N];
inline void add(int u,int v,int w){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    e[cnt].w=w;
    head[u]=cnt;
}
int fa[N];
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x] = find(fa[x]);
}
inline void build(int k){
    for(int i=1;i<=n;i++) fa[i]=i;
    cnt=0;
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    for(int i=1;i<=m;i++){
        int u=x[i],v=y[i],w=(z[i]>>(k-1)) & 1ll;
        int U=find(u),V=find(v);
        if(U==V) continue;
        fa[U]=V;
        add(u,v,w);
        add(v,u,w);
    }
    return;
}
int f[N][2];
inline void dfs(int u){
    f[u][0]=0,f[u][1]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(f[v][0]==-1){
            dfs(v);
            f[u][0]+=f[v][w];
            f[u][1]+=f[v][1^w];
        }
    }
    return;
}
bool vis[N];
inline void upd(int u,bool flag,int k){
    if(flag) ans[u]|=(1ll<<(k-1));
    vis[u]=true;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to,w=e[i].w;
        if(!vis[v]) upd(v,(flag^w),k);
    }
    return;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>x[i]>>y[i]>>z[i];
    for(int i=1;i<=40;i++){
        build(i);
        memset(f,-1,sizeof(f));
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++){
            if(f[j][0]==-1){
                dfs(j);
                if(f[j][0]<f[j][1]) upd(j,0,i);
                else upd(j,1,i);
            }
        }
    }
    for(int i=1;i<=m;i++){
        if((ans[x[i]]^ans[y[i]])!=z[i]){
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}