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

• 問題: No.3781 Erase One, Gain from the Other
• ユーザー: HoyHoyCharhang
• 提出日時: 2026-10-30 23:43:36
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 437 ms / 2,000 ms
• コード長: 5,239 bytes
• コンパイル時間: 3,549 ms
• コンパイル使用メモリ: 366,152 KB
• 実行使用メモリ: 46,244 KB
• 最終ジャッジ日時: 2026-10-30 23:43:54
• 合計ジャッジ時間: 17,538 ms
• ジャッジサーバーID （参考情報）: judge7_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define eb emplace_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using P = pair<int,int>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}

// https://ei1333.github.io/algorithm/graph.html
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 > >;
template< typename T >
using Matrix = vector< vector< T > >;

// https://ei1333.github.io/algorithm/union-find.html
struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

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

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

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

// https://ei1333.github.io/algorithm/skew-heap.html
template< typename T, typename E = T >
struct SkewHeap
{
  using G = function< T(T, E) >;
  using H = function< E(E, E) >;

  struct Node
  {
    T key;
    E lazy;
    Node *l, *r;
  };

  const bool rev;
  const G g;
  const H h;

  SkewHeap(bool rev = false) : g([](const T &a, const E &b) { return a + b; }),
                               h([](const E &a, const E &b) { return a + b; }), rev(rev) {}

  SkewHeap(const G &g, const H &h, bool rev = false) : g(g), h(h), rev(rev) {}

  Node *propagate(Node *t)
  {
    if(t->lazy != 0) {
      if(t->l) t->l->lazy = h(t->l->lazy, t->lazy);
      if(t->r) t->r->lazy = h(t->r->lazy, t->lazy);
      t->key = g(t->key, t->lazy);
      t->lazy = 0;
    }
    return t;
  }

  Node *merge(Node *x, Node *y)
  {
    if(!x || !y) return x ? x : y;
    propagate(x), propagate(y);
    if((x->key > y->key) ^ rev) swap(x, y);
    x->r = merge(y, x->r);
    swap(x->l, x->r);
    return x;
  }

  void push(Node *&root, const T &key)
  {
    root = merge(root, new Node({key, 0, nullptr, nullptr}));
  }

  T top(Node *root)
  {
    return propagate(root)->key;
  }

  void pop(Node *&root)
  {
    propagate(root);
    auto *temp = root;
    root = merge(root->l, root->r);
    delete temp;
  }

  bool empty(Node *root) const
  {
    return !root;
  }

  void add(Node *root, const E &lazy)
  {
    if(root) {
      root->lazy = h(root->lazy, lazy);
      propagate(root);
    }
  }

  Node *makeheap()
  {
    return nullptr;
  }
};

// https://ei1333.github.io/algorithm/chu-liu-edmond.html
template< typename T >
struct MinimumSpanningTreeArborescence
{
  using Pi = pair< T, int >;
  using Heap = SkewHeap< Pi, int >;
  using Node = typename Heap::Node;
  const Edges< T > &es;
  const int V;
  T INF;
 
  MinimumSpanningTreeArborescence(const Edges< T > &es, int V) :
      INF(numeric_limits< T >::max()), es(es), V(V) {}
 
  T build(int start)
  {
    auto g = [](const Pi &a, const T &b) { return Pi(a.first + b, a.second); };
    auto h = [](const T &a, const T &b) { return a + b; };
    Heap heap(g, h);
    vector< Node * > heaps(V, heap.makeheap());
    for(auto &e : es) heap.push(heaps[e.to], {e.cost, e.src});
    UnionFind uf(V);
    vector< int > used(V, -1);
    used[start] = start;
 
    T ret = 0;
    for(int s = 0; s < V; s++) {
      stack< int > path;
      for(int u = s; used[u] < 0;) {
        path.push(u);
        used[u] = s;
        if(heap.empty(heaps[u])) return -1;
        auto p = heap.top(heaps[u]);
        ret += p.first;
        heap.add(heaps[u], -p.first);
        heap.pop(heaps[u]);
        int v = uf.find(p.second);
        if(used[v] == s) {
          int w;
          Node *nextheap = heap.makeheap();
          do {
            w = path.top();
            path.pop();
            nextheap = heap.merge(nextheap, heaps[w]);
          } while(uf.unite(v, w));
          heaps[uf.find(v)] = nextheap;
          used[uf.find(v)] = -1;
        }
        u = uf.find(v);
      }
    }
    return ret;
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  rep(i,0,n) cin >> a[i];
  Edges<ll> es;
  rep(i,0,m) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    es.eb(u, v, -a[u]), es.eb(v, u, -a[v]);
  }
  rep(i,0,n) {
    es.eb(n, i, 0);
  }
  MinimumSpanningTreeArborescence<ll> msta(es, n+1);
  cout << -msta.build(n) << endl;
}

int main() {
  int t;
  cin >> t;
  while(t--) solve();
  return 0;
}