图上交互题题解

~~这题赛时竟然灵感突发做出来了，所以来水一发题解（~~

这道题实际上就是让我们通过路径最小异或代价来构建合法的边权值。我们需要分析给定的边及其对应的代价，并构建一个合法的边权值，使得所有路径的异或代价符合这些要求。每条边的代价是未知的，我们需要根据输入的代价来推出每条边的权值。

定义路径代价为所经过边权值的异或。对于任意两点和，我们需要确保从到的所有路径中，最小的代价为。

若有环，并且在环上进行异或运算，环的代价应当为。如果，则可以推导出边的权值。我们可以利用并查集来维护，并进行路径压缩和合并。在每次合并两个点和时，记录边的权值。

对于每条边，我们可以构建一个方程：

（其中和为已知值）

对于每对节点和，可以通过并查集查找到它们的根节点，并确保它们在同一个连通分量中，然后就可以利用异或来逐步构建出合法的边权值。并且在合并的过程中，要检查是否存在矛盾。若有矛盾，直接输出NO即可。

完整代码如下

#include <iostream>
#include <vector>
#include <unordered_map>
#include <tuple>
#include <cstdio>

#define int long long
#define function auto
#define rop(a, b, c) for(int a = b; a < c; ++ a)
#define por(a, b, c) for(int a = b; a > c; -- a)
#define rep(a, b, c) for(int a = b; a <= c; ++ a)
#define per(a, b, c) for(int a = b; a >= c; -- a)

namespace Space {

    template < typename _Tp > inline function
    read(_Tp& t) -> void {
        int f = 0, ch = getchar (); t = 0;
        while (!isdigit (ch)) f |= (ch == '-'), ch = getchar ();
        do {t = (t << 1) + (t << 3) + (ch & 15); ch = getchar ();}
        while (isdigit(ch)); t = f ? -t : t;
    }

    template < typename _Tp, typename... _Args > inline function
    read(_Tp& t, _Args&... args) -> void {read(t); read(args...);}
}

using namespace Space;

class Find {
public:
    std::vector<int> parent, rank, xorValue;
    
    Find(int n) : parent(n), rank(n, 0), xorValue(n, 0) {
        rop(i, 0, n) parent[i] = i;
    }
public:
    inline function
    find(int x) -> int {
        if (parent[x] != x) {
            int root = this -> find(parent[x]);
            xorValue[x] ^= xorValue[parent[x]];
            parent[x] = root;
        } return parent[x];
    }

    inline function
    uunion(int x, int y, int value) -> bool {
        int rootX = this -> find(x);
        int rootY = this -> find(y);
        if (rootX == rootY) return (xorValue[x] ^ xorValue[y]) == value;
        if (rank[rootX] < rank[rootY])std::swap(rootX, rootY);
        parent[rootY] = rootX;
        xorValue[rootY] = xorValue[x] ^ xorValue[y] ^ value;
        if (rank[rootX] == rank[rootY])rank[rootX] ++;
        return true;
    }
};

signed main() {
    int n, m;read(n, m);
    std::vector<int> u(m), v(m), f(m);
    rop(i, 0, m){
        read(u[i], v[i], f[i]);
        -- u[i]; -- v[i];
    }
    Find uf(n); bool possible = true;
    rop(i, 0, m) {
        if (!uf.uunion(u[i], v[i], f[i])) {
            possible = false; break;
        }
    } if (!possible) std::printf("No\n");
    else {
        std::printf("Yes\n");
        std::vector<int> a(m, 0);
        rop(i, 0, m) a[i] = f[i];
        for (auto x : a) std::cout << x << ' ';
        std::printf("\n");
    } return 0;
}

__DIOsama__

图上交互题题解

DIOsama