[ABC396E] Min of Restricted Sum 题解

· · 题解

[ABC396E] Min of Restricted Sum 题解

原题链接

思路

将每对 x_i,y_i,z_i 建为无向图。设 a_i 为节点 i 的值，对于每个连通块预设根节点值为 0，进行BFS。对于一条从 x 连向 y 的边，若 a_y 有值，则判断 x_i\oplus y_i 是否等于 z_i，若不等于则无解。若 a_y 无值，则设 y_i=x_i\oplus z_i。

得出一组解后，对于每个连通块，按位看，因为所有值按位取反后结果不变，所以若这个连通块中的所有解中，当前位为 1 的数量比 0 多，则能使答案和变小。

// Problem: E - Min of Restricted Sum
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_e
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// Date: 2025-03-08 20:15:02
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mst(x, y) memset(x, y, sizeof(x))
#define pii pair<int, int>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

int read(){int x = 0, f = 1;char c = getchar();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9'){x = 10*x+c-'0';c = getchar();}return f*x;}
void writ(int x){if(x < 0){putchar('-');x = -x;}if(x > 9) writ(x/10);putchar(x%10 | 0x30);return;}
void write(int x){writ(x);puts("");}
void wr(int x){writ(x);putchar(' ');}
const int N = 2000005, inf = 0x3f3f3f3f;

int n, m, d[N], idx;
int hd[N], ver[N], nxt[N], val[N];
queue <int> q;

void add(int x, int y, int w){
    nxt[++idx] = hd[x];
    ver[idx] = y;
    val[idx] = w;
    hd[x] = idx;
}
int bfs(){
    mst(d, -1);
    for(int x = 1;x <= n;x++){
        vector <pii> v;
        if(d[x] == -1){
            while(q.size()) q.pop();
            q.push(x);
            d[x] = 0;
            while(q.size()){
                int t = q.front();
                q.pop();
                v.push_back(mp(d[t], t));
                for(int i = hd[t];i;i = nxt[i]){
                    int y = ver[i];
                    if(d[y] == -1){
                        d[y] = d[t]^val[i];
                        q.push(y);
                    }
                    else if(d[y] != (d[t]^val[i])){
                        write(-1);
                        return 1;
                    }
                }
            }
            int xorr = 0;
            for(int j = 31;j >= 0;j--){
                int mod = (1<<j), cnt1 = 0, cnt2 = 0;
                for(int i = 0;i < v.size();i++){
                    if(d[v[i].se]&mod) cnt1++;
                    else cnt2++;
                }
                if(cnt1 >= cnt2){
                    xorr |= mod;
                }
            }
            for(int i = 0;i < v.size();i++){
                d[v[i].se] ^= xorr;
            }
        }
    }
    return 0;
}
void init(){
    n = read(), m = read();
    for(int i = 1;i <= m;i++){
        int x = read(), y = read(), w = read();
        add(x, y, w); add(y, x, w);
    }
}
void solve(){   
    if(bfs()) return;
    for(int i = 1;i <= n;i++) wr(d[i]);
}

signed main(){
    init();
    solve();
    return 0; 
}