AtCoder ABC E - Min of Restricted Sum 题解

根据输入考虑建图，x、y两个下标的边权为z,建无向图

这样我们可以得到一些连通块。根据异或和的性质，对于每一个连通块，我们只要知道其中一个点的点权就能推出所有的点权。

最小值考虑贪心，针对当前连通图所有点权二进制数的每一位，假如这一位是1，要想保留更多的1就让别的本位为1的数的这一位是0，于是统计每一位1的个数，若1比0多则起点这一位为1，这样保证了0多。

判定可行性：深搜跑一边，如果遍历过了但是点权不符合多个边的要求，那麽就是无解

int head[N], IDX = 0;struct NODE{int t, ne;ll w=0;}ed[N];
void add(int s,int t,ll w){
    ed[++IDX].ne = head[s]; ed[IDX].t = t; head[s] = IDX;
    ed[IDX].w = w;
}
ll n,m;
ll x,y,z,tmp;
bool vis[N];
int val[N],bit[35],ans[N];
map <PII,bool> hse;
bool f = 1;
void dfs1(int now,int st)
{
    tmp++;
    val[now] = st;
    vis[now] = 1;
    for(int i=0;i<32;i++)
    {
        if(st>>i&1)
        {
            bit[i]++;
        }
    }
    for(int i=head[now];i;i=ed[i].ne)
    {
        int t = ed[i].t;
        int w = ed[i].w;
        if(!vis[t])
        {
            dfs1(t,st^w);
        }
        else
        {
            //cout<<val[t]<<' '<<(st^w)<<endl;
            if(val[t]!=(st^w))
            {
                f=0;
                return ;
            }
        }
    }
}
void dfs2(int now)
{
    vis[now] = 1;
    for(int i=head[now];i;i=ed[i].ne)
    {
        int t = ed[i].t;
        if(!vis[t])
        {
            ans[t] = (ans[now]^ed[i].w);
            dfs2(t);
        }
    }
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            for(int j=0;j<32;j++)
            {
                bit[j]=0;
            }
            tmp=1;
            dfs1(i,0);
            //cout<<tmp<<endl;
            if(f==0)
            {
                cout<<-1<<endl;
                return ;
            }
            for(int j=0;j<32;j++)
            {
                if(bit[j]>=tmp-bit[j])
                {
                    ans[i]|=1<<j;
                }
            }
        }
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs2(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<' ';
    }
}