Codeforces Round #715 (Div. 1) C. Complete the MST

問題リンク

解説

補グラフにおいて, 1 つは XOR の値を,それ以外は全て 0 として損をしません.

補グラフにおける辺をいったん全てコスト 0 としてすべてつなげます.そして,元のグラフの分をクラスカル法の要領でくっつけていきます.

補グラフにサイクルを含むとき

サイクルの 1 つに XOR の値をおしつければいいので,捕グラフの辺のコストを全て 0 と考えても問題なく,おしまいです.

補グラフが森の時

このとき,捕グラフでつなげた連結成分のどこかの1つを加算しなければなりません.加算するのは, XOR と 補グラフの連結成分の頂点組であり,元のグラフでクラスカルの要領でくっつけた辺だけでは連結ではない頂点組のコスト最小値の小さい方です.

実装例

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <array>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>
#include <valarray>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

namespace KKT89
{
  struct UnionFind
  {
    std::vector<int> par;
    UnionFind(int n)
    {
        par.assign(n, -1);
    }
    int root(int a)
    {
        if (par[a] < 0)
        {
            return a;
        }
        return par[a] = root(par[a]);
    }

    int size(int a)
    {
        return -par[root(a)];
    }
    bool connect(int a, int b)
    {
        a = root(a);
        b = root(b);
        if (a == b)
        {
            return false;
        }
        if (size(a) < size(b))
        {
            std::swap(a, b);
        }

        par[a] += par[b];
        par[b] = a;

        return true;
    }
    bool same(int a, int b)
    {
        return root(a) == root(b);
    }
  };
}

void solve()
{
    int n, m; cin >> n >> m;
    std::vector<std::tuple<int, int, int>> edges; edges.reserve(m);
    std::vector<std::pair<int, int>> vp; vp.reserve(m);
    int XOR = 0;
    for (int i = 0; i < m; ++i)
    {
        int u, v, w; cin >> u >> v >> w;
        u -= 1, v -= 1;
        if(u > v)
            std::swap(u, v);
        XOR ^= w;
        edges.emplace_back(w, u, v);
        vp.emplace_back(u, v);
    }
    std::sort(edges.begin(), edges.end());
    std::sort(vp.begin(), vp.end());
    auto edge_exist = [&](int u, int v)
    {
        if(u > v)
            std::swap(u, v);
        return std::binary_search(vp.begin(), vp.end(), std::make_pair(u, v));
    };
    std::set<int> s;
    for (int i = 0; i < n; ++i)
    {
        s.emplace(i);
    }
    KKT89::UnionFind uf1(n), uf2(n);
    int cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        if(s.find(i) == s.end())
            continue;
        std::queue<int> q;
        q.emplace(i);
        s.erase(s.find(i));
        while(not q.empty())
        {
            const int cur = q.front();
            q.pop();
            for(auto itr = s.begin(); itr != s.end();)
            {
                if(not edge_exist(cur, *itr))
                {
                    q.emplace(*itr);
                    uf1.connect(cur, *itr);
                    itr = s.erase(itr);
                }
                else
                {
                    itr = std::next(itr);
                }
            }
        }
        cnt += 1;
    }
    int min = XOR;
    ll res = 0;
    for(const auto &[w, u, v] : edges)
    {
        if(uf1.same(u, v) and not uf2.same(u, v))
        {
            chmin(min, w);
        }
        if(uf1.connect(u, v) and uf2.connect(u, v))
            res += w;
    }
    if(n - (1LL * n * (n - 1) / 2 - m) == cnt)
    {
        res += min;
    }
    cout << res << "\n";
}
int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int kkt = 1;
  //cin >> kkt;
  while(kkt--)
    solve();
  return 0;
}