#1196049 (C++17) No.3781 Erase One, Gain from the Other

• 問題: No.3781 Erase One, Gain from the Other
• ユーザー: Rubikun
• 提出日時: 2026-10-30 22:06:15
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 602 ms / 2,000 ms
• コード長: 6,459 bytes
• コンパイル時間: 1,805 ms
• コンパイル使用メモリ: 238,376 KB
• 実行使用メモリ: 101,976 KB
• 最終ジャッジ日時: 2026-10-30 22:06:35
• 合計ジャッジ時間: 15,729 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

// https://ei1333.github.io/library/graph/mst/directed-mst.hpp

#line 2 "graph/mst/directed-mst.hpp"

#include <vector>

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

#include <cassert>
#include <utility>

/**
 * @brief Skew-Heap
 */
template <typename T, bool isMin = true>
struct SkewHeap {
    struct Node {
        T key, lazy;
        Node *l, *r;
        int idx;
        
        explicit Node(const T& key, int idx)
        : key(key), lazy(0), l(nullptr), r(nullptr), idx(idx) {}
    };
    
    SkewHeap() = default;
    
    Node* alloc(const T& key, int idx = -1) { return new Node(key, idx); }
    
    Node* propagate(Node* t) {
        if (t && t->lazy != 0) {
            if (t->l) t->l->lazy += t->lazy;
            if (t->r) t->r->lazy += t->lazy;
            t->key += t->lazy;
            t->lazy = 0;
        }
        return t;
    }
    
    Node* meld(Node* x, Node* y) {
        propagate(x), propagate(y);
        if (!x || !y) return x ? x : y;
        if ((x->key < y->key) ^ isMin) std::swap(x, y);
        x->r = meld(y, x->r);
        std::swap(x->l, x->r);
        return x;
    }
    
    Node* push(Node* t, const T& key, int idx = -1) {
        return meld(t, alloc(key, idx));
    }
    
    Node* pop(Node* t) {
        assert(t != nullptr);
        return meld(t->l, t->r);
    }
    
    Node* add(Node* t, const T& lazy) {
        if (t) {
            t->lazy += lazy;
            propagate(t);
        }
        return t;
    }
    
    Node* make_root() { return nullptr; }
};
#line 2 "graph/graph-template.hpp"

#include <cstddef>
#include <iostream>
#line 6 "graph/graph-template.hpp"

template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    int idx;
    
    Edge() = default;
    
    Edge(int from, int to, T cost = 1, int idx = -1)
    : from(from), to(to), cost(cost), idx(idx) {}
    
    operator int() const { return to; }
};

template <typename T = int>
struct Graph {
    std::vector<std::vector<Edge<T> > > g;
    int es;
    
    Graph() = default;
    
    explicit Graph(int n) : g(n), es(0) {}
    
    std::size_t size() const { return g.size(); }
    
    void add_directed_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es++);
    }
    
    void add_edge(int from, int to, T cost = 1) {
        g[from].emplace_back(from, to, cost, es);
        g[to].emplace_back(to, from, cost, es++);
    }
    
    void read(int M, int padding = -1, bool weighted = false,
              bool directed = false) {
        for (int i = 0; i < M; i++) {
            int a, b;
            std::cin >> a >> b;
            a += padding;
            b += padding;
            T c = T(1);
            if (weighted) std::cin >> c;
            if (directed)
                add_directed_edge(a, b, c);
            else
                add_edge(a, b, c);
        }
    }
    
    inline std::vector<Edge<T> >& operator[](const int& k) { return g[k]; }
    
    inline const std::vector<Edge<T> >& operator[](const int& k) const {
        return g[k];
    }
};

template <typename T = int>
using Edges = std::vector<Edge<T> >;
#line 7 "graph/mst/directed-mst.hpp"

/**
 * @brief Directed MST(最小有向全域木)
 *
 */
template <typename T>
struct MinimumSpanningTree {
    T cost;
    Edges<T> edges;
};

template <typename T>
MinimumSpanningTree<T> directed_mst(int V, int root, Edges<T> edges) {
    for (int i = 0; i < V; ++i) {
        if (i != root) edges.emplace_back(i, root, 0);
    }
    
    int x = 0;
    std::vector<int> par(2 * V, -1), vis(par), link(par);
    
    using Heap = SkewHeap<T, true>;
    using Node = typename Heap::Node;
    
    Heap heap;
    std::vector<Node*> ins(2 * V, heap.make_root());
    
    for (int i = 0; i < (int)edges.size(); i++) {
        auto& e = edges[i];
        ins[e.to] = heap.push(ins[e.to], e.cost, i);
    }
    std::vector<int> st;
    auto go = [&](int x) {
        x = edges[ins[x]->idx].from;
        while (link[x] != -1) {
            st.emplace_back(x);
            x = link[x];
        }
        for (auto& p : st) {
            link[p] = x;
        }
        st.clear();
        return x;
    };
    for (int i = V; ins[x]; i++) {
        for (; vis[x] == -1; x = go(x)) vis[x] = 0;
        for (; x != i; x = go(x)) {
            auto w = ins[x]->key;
            auto v = heap.pop(ins[x]);
            v = heap.add(v, -w);
            ins[i] = heap.meld(ins[i], v);
            par[x] = i;
            link[x] = i;
        }
        for (; ins[x] && go(x) == x; ins[x] = heap.pop(ins[x]));
    }
    T cost = 0;
    Edges<T> ans;
    for (int i = root; i != -1; i = par[i]) {
        vis[i] = 1;
    }
    for (int i = x; i >= 0; i--) {
        if (vis[i] == 1) continue;
        cost += edges[ins[i]->idx].cost;
        ans.emplace_back(edges[ins[i]->idx]);
        for (int j = edges[ins[i]->idx].to; j != -1 && vis[j] == 0; j = par[j]) {
            vis[j] = 1;
        }
    }
    return {cost, ans};
}


int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        ll N,M;cin>>N>>M;
        vl A(N);
        for(int i=0;i<N;i++){
            cin>>A[i];
        }
        Edges<ll> edges;
        vector<array<ll,3>> E(M);
        for(int i=0;i<M;i++){
            ll a,b;cin>>a>>b;a--;b--;
            edges.emplace_back(a,b,INF-A[a]);
            edges.emplace_back(b,a,INF-A[b]);
        }
        for(int i=0;i<N;i++) edges.emplace_back(N,i,INF-0);
        cout<<(ll)(INF)*N-directed_mst(N+1,N,edges).cost<<"\n";
    }
}