#1197737 (C++23(gcc16)) No.3781 Erase One, Gain from the Other

• 問題: No.3781 Erase One, Gain from the Other
• ユーザー: C
• 提出日時: 2026-11-08 16:58:13
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 153 ms / 2,000 ms
• コード長: 7,702 bytes
• コンパイル時間: 7,885 ms
• コンパイル使用メモリ: 400,036 KB
• 実行使用メモリ: 65,196 KB
• 最終ジャッジ日時: 2026-11-08 16:58:33
• 合計ジャッジ時間: 18,434 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge4_0

ファイルパターン	結果
sample	AC * 1
other	AC * 34

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;

#line 2 "graph/minimum-cost-arborescence.hpp"

#line 2 "data-structure/skew-heap.hpp"

template <typename T, bool isMin = true>
struct SkewHeap {
  struct Node {
    T key, laz;
    Node *l, *r;
    int idx;
    Node() = default;
    Node(const T &k, int i = -1)
        : key(k), laz(0), l(nullptr), r(nullptr), idx(i) {}
  };
  using Ptr = Node *;

  static void propagate(Ptr x) {
    if (x->laz == 0) return;
    if (x->l) x->l->laz += x->laz;
    if (x->r) x->r->laz += x->laz;
    x->key += x->laz;
    x->laz = 0;
  }

  static Ptr meld(Ptr x, Ptr y) {
    if (!x || !y) return x ? x : y;
    if (!comp(x, y)) swap(x, y);
    propagate(x);
    x->r = meld(x->r, y);
    swap(x->l, x->r);
    return x;
  }

  static Ptr alloc(const T &key, int idx = -1) { return new Node(key, idx); }

  static Ptr pop(Ptr x) {
    propagate(x);
    return meld(x->l, x->r);
  }

  static Ptr push(Ptr x, const T &key, int idx = -1) {
    return meld(x, alloc(key, idx));
  }

  static void apply(Ptr x, const T &laz) {
    x->laz += laz;
    propagate(x);
  }

 private:
  static inline bool comp(Ptr x, Ptr y) {
    if constexpr (isMin) {
      return x->key + x->laz < y->key + y->laz;
    } else {
      return x->key + x->laz > y->key + y->laz;
    }
  }
};

/**
 * @brief Skew Heap
 * @docs docs/data-structure/skew-heap.md
 */
#line 2 "data-structure/union-find.hpp"

struct UnionFind {
  vector<int> data;
  UnionFind(int N) : data(N, -1) {}

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return true;
  }

  // f(x, y) : x に y をマージ
  template<typename F>
  int unite(int x, int y,const F &f) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    f(x, y);
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }
};

/**
 * @brief Union Find(Disjoint Set Union)
 * @docs docs/data-structure/union-find.md
 */
#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N, int M, int is_weighted = true,
                 bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 6 "graph/minimum-cost-arborescence.hpp"

template <typename T>
Edges<T> MinimumCostArborescence(int N, int root, const Edges<T> &es) {
  using Heap = SkewHeap<T>;
  using Ptr = typename Heap::Ptr;
  UnionFind uf(N);
  vector<int> used(N, -1), from(N);
  vector<T> from_cost(N);
  vector<Ptr> come(N, nullptr);

  used[root] = root;
  vector<int> par_e(es.size(), -1), stem(N, -1), idxs;

  for (int i = 0; i < (int)es.size(); i++) {
    auto &e = es[i];
    come[e] = Heap::push(come[e], e.cost, i);
  }

  T costs = 0;

  for (int start = 0; start < N; start++) {
    if (used[start] != -1) continue;
    int cur = start;
    vector<int> chi_e;
    int cycle = 0;
    while (used[cur] == -1 || used[cur] == start) {
      used[cur] = start;
      if (come[cur] == nullptr) return {};
      int src = uf.find(es[come[cur]->idx].src);
      T cost = come[cur]->key + come[cur]->laz;
      int idx = come[cur]->idx;
      come[cur] = Heap::pop(come[cur]);
      if (src == cur) continue;

      from[cur] = src;
      from_cost[cur] = cost;
      if (stem[cur] == -1) stem[cur] = idx;
      costs += cost;
      idxs.push_back(idx);
      while (cycle) {
        par_e[chi_e.back()] = idx;
        chi_e.pop_back();
        --cycle;
      }
      chi_e.push_back(idx);

      if (used[src] == start) {
        int p = cur;
        do {
          if (come[p]) Heap::apply(come[p], -from_cost[p]);
          if (p != cur) {
            uf.unite(p, cur);
            Ptr newheap = Heap::meld(come[cur], come[p]);
            come[cur = uf.find(cur)] = newheap;
          }
          p = uf.find(from[p]);
          ++cycle;
        } while (p != cur);
      } else {
        cur = src;
      }
    }
  }

  vector<int> used_e(es.size());
  Edges<T> res;
  for (int _ = (int)idxs.size(); _--;) {
    int idx = idxs[_];
    if (used_e[idx]) continue;
    auto &e = es[idx];
    res.push_back(e);
    int x = stem[e.to];
    while (x != idx) {
      used_e[x] = true;
      x = par_e[x];
    }
  }
  return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--){
		int N,M;
		cin>>N>>M;
		vll A(N+1);
		rep(i,1,N+1)cin>>A[i];
		Edges<ll>es;
		while(M--){
			int u,v;
			cin>>u>>v;
			es.push_back({v,u,-A[v]});
			es.push_back({u,v,-A[u]});
		}
		rep(u,1,N+1)es.push_back({0,u,0});
		auto tree=MinimumCostArborescence(N+1,0,es);
		ll ans=0;
		for(auto&e:tree)ans-=e.cost;
		cout<<ans<<'\n';
	}
}