#1185392 (C++23) No.3699 引き抜き交渉

• 問題: No.3699 引き抜き交渉
• ユーザー: askr58
• 提出日時: 2026-09-09 21:52:36
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 10,742 bytes
• コンパイル時間: 3,592 ms
• コンパイル使用メモリ: 344,292 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-09-09 21:52:42
• 合計ジャッジ時間: 5,409 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge4_0

ファイルパターン	結果
sample	AC * 2
other	AC * 15

ソースコード

#include <iostream>
#include <random>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <ranges>
#include <algorithm>
#include <vector>
using namespace std;
using ll=long long;

#include <atcoder/all>
using mint=atcoder::modint998244353;

ostream& operator<<(ostream& os,const mint& x){
	os<<x.val();
	return os;
}
istream& operator>>(istream& is,mint& x){
	int t;
	is>>t;
	x=t;
	return is;
}

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p);
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p);
template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr);
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr);
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec);
template <typename T>
istream& operator>>(istream& is,vector<T>& vec);

template <typename S,typename T>
ostream& operator<<(ostream& os,const pair<S,T>& p){
	os<<p.first<<" "<<p.second;
	return os;
}
template <typename S,typename T>
istream& operator>>(istream& is,pair<S,T>& p){
	is>>p.first>>p.second;
	return is;
}

template <typename T,size_t n>
ostream& operator<<(ostream& os,const array<T,n>& arr){
	for(int i=0;i<n;i++)os<<arr[i]<<(i+1==n?"":" ");
	return os;
}
template <typename T,size_t n>
istream& operator>>(istream& is,array<T,n>& arr){
	for(int i=0;i<n;i++)is>>arr[i];
	return is;
}
template <typename T>
ostream& operator<<(ostream& os,const vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)os<<vec[i]<<(i+1==(int)vec.size()?"":" ");
	return os;
}
template <typename T>
istream& operator>>(istream& is,vector<T>& vec){
	for(int i=0;i<(int)vec.size();i++)is>>vec[i];
	return is;
}

template<class... Vecs>
void input_vec(Vecs&... vs) {
    const auto n = get<0>(tie(vs...)).size();

    for (size_t i = 0; i < n; ++i)
        ((cin >> vs[i]), ...);
}

template <typename T>
vector<T> make_unique(vector<T> vec){
	ranges::sort(vec);
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	return vec;
}

template <typename T, typename Comp = ranges::less, typename Proj = identity>
pair<vector<int>,vector<int>> make_rank(const vector<T>& vec, Comp comp = {}, Proj proj = {}) {
    int n = vec.size();
    vector<int> argsort(n);
    iota(argsort.begin(), argsort.end(), 0);

    ranges::stable_sort(argsort, comp, [&](int i) -> decltype(auto) {
        return invoke(proj, vec[i]);
    });

	vector<int> rank(n);
	for(int i=0;i<n;i++)rank[argsort[i]]=i;
    return make_pair(rank,argsort);
}

void YESNO(bool f){
	if(f)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using vvvl=vector<vector<vector<ll>>>; 
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vvvi=vector<vector<vector<int>>>;

//Generated by ChatGPT outside of contest time.
#include <atcoder/maxflow>
#include <cassert>
#include <vector>
#include <utility>

class MongeMinCut {
public:
    using ll = long long;

    static constexpr ll INF = 1'000'000'000'000'000'000LL;

    struct Result {
        ll cost;
        std::vector<int> values;
    };

private:
    int n_;       // 変数の数
    int k_;       // 各変数が取る値の数

    int source_;
    int sink_;

    atcoder::mf_graph<ll> graph_;

    // graph 上の cut cost にこれを足すと、本来の目的関数になる。
    ll offset_ = 0;

    bool solved_ = false;

    /*
     * 変数 var に対して
     *
     *     vertex_id(var, value) が S 側
     *
     * であることを
     *
     *     x_var >= value
     *
     * と解釈する。
     *
     * value = 1, ..., k-1 のみ頂点を持つ。
     * value = 0 は常に x_var >= 0 なので頂点不要。
     */
    int vertex_id(int var, int value) const {
        assert(0 <= var && var < n_);
        assert(1 <= value && value < k_);

        // 頂点番号の具体的な割り当てはこの関数内に閉じ込める。
        return var * (k_ - 1) + (value - 1);
    }

    /*
     * 頂点 v の indicator
     *
     *     z = [v が S 側]
     *
     * に対して coeff * z というコストを追加する。
     */
    void add_indicator_cost(int v, ll coeff) {
        if (coeff >= 0) {
            /*
             * v が S 側のときだけ v -> t が cut される。
             *
             * cut cost = coeff * z
             */
            if (coeff != 0) {
                graph_.add_edge(v, sink_, coeff);
            }
        } else {
            /*
             * s -> v を容量 -coeff で張る。
             *
             * cut cost
             *   = (-coeff) * (1-z)
             *   = -coeff + coeff*z
             *
             * よって offset に coeff を足せば
             *
             *   cut cost + coeff = coeff*z
             *
             * になる。
             */
            graph_.add_edge(source_, v, -coeff);
            offset_ += coeff;
        }
    }

public:
    /*
     * n : 変数の数
     * k : 各変数が取る値の数
     *
     * x_i in {0, 1, ..., k-1}
     */
    MongeMinCut(int n, int k)
        : n_(n),
          k_(k),
          source_(n * (k - 1)),
          sink_(source_ + 1),
          graph_(sink_ + 1) {

        assert(n_ >= 0);
        assert(k_ >= 1);

        /*
         * [x >= value+1] = 1 なら
         * [x >= value]   = 1
         *
         * でなければならない。
         *
         * したがって
         *
         *     vertex(value+1) -> vertex(value)
         *
         * に INF を張る。
         */
        for (int var = 0; var < n_; ++var) {
            for (int value = 1; value + 1 < k_; ++value) {
                graph_.add_edge(
                    vertex_id(var, value + 1),
                    vertex_id(var, value),
                    INF
                );
            }
        }
    }

    /*
     * unary cost を追加する。
     *
     * cost[value] = x_var = value のときのコスト
     */
    void add_unary_cost(
        int var,
        const std::vector<ll>& cost
    ) {
        assert(!solved_);
        assert(0 <= var && var < n_);
        assert((int)cost.size() == k_);

        /*
         * telescoping:
         *
         * cost[x]
         * =
         * cost[0]
         * + sum_{p=1}^{k-1}
         *     (cost[p] - cost[p-1]) [x >= p]
         */
        offset_ += cost[0];

        for (int p = 1; p < k_; ++p) {
            ll coeff = cost[p] - cost[p - 1];

            add_indicator_cost(
                vertex_id(var, p),
                coeff
            );
        }
    }

    /*
     * pairwise cost を追加する。
     *
     * cost[x][y]
     * =
     *   x_var1 = x,
     *   x_var2 = y
     *
     * のときのコスト。
     *
     * Monge:
     *
     * cost[p-1][q-1] + cost[p][q]
     * <=
     * cost[p-1][q]   + cost[p][q-1]
     *
     * を仮定する。
     */
    void add_pairwise_cost(
        int var1,
        int var2,
        const std::vector<std::vector<ll>>& cost
    ) {
        assert(!solved_);
        assert(0 <= var1 && var1 < n_);
        assert(0 <= var2 && var2 < n_);
        assert((int)cost.size() == k_);

        for (const auto& row : cost) {
            assert((int)row.size() == k_);
        }

        /*
         * 以下の恒等式を使う。
         *
         * u_p = [x >= p]
         * v_q = [y >= q]
         *
         * とすると
         *
         * C(x,y)
         * =
         * C(0,0)
         * + sum_p a_p u_p
         * + sum_q b_q v_q
         * + sum_{p,q} w_{pq} u_p (1-v_q)
         *
         * ただし
         *
         * a_p = C(p,k-1) - C(p-1,k-1)
         *
         * b_q = C(0,q) - C(0,q-1)
         *
         * w_pq
         * = C(p-1,q) + C(p,q-1)
         *   - C(p-1,q-1) - C(p,q)
         *
         * Monge 性より w_pq >= 0。
         */

        offset_ += cost[0][0];

        const int last = k_ - 1;

        // a_p [x >= p]
        for (int p = 1; p < k_; ++p) {
            ll a =
                cost[p][last]
                - cost[p - 1][last];

            add_indicator_cost(
                vertex_id(var1, p),
                a
            );
        }

        // b_q [y >= q]
        for (int q = 1; q < k_; ++q) {
            ll b =
                cost[0][q]
                - cost[0][q - 1];

            add_indicator_cost(
                vertex_id(var2, q),
                b
            );
        }

        /*
         * w_pq [x >= p] [y < q]
         *
         * vertex(var1,p) -> vertex(var2,q)
         *
         * が cut されるのは
         *
         *   x >= p
         *   y < q
         *
         * のときだけ。
         */
        for (int p = 1; p < k_; ++p) {
            for (int q = 1; q < k_; ++q) {
                ll w =
                    cost[p - 1][q]
                    + cost[p][q - 1]
                    - cost[p - 1][q - 1]
                    - cost[p][q];

                // Monge 性
                assert(w >= 0);

                if (w != 0) {
                    graph_.add_edge(
                        vertex_id(var1, p),
                        vertex_id(var2, q),
                        w
                    );
                }
            }
        }
    }

    /*
     * 最適化を実行する。
     *
     * result.cost
     *   最小コスト
     *
     * result.values[i]
     *   変数 i の最適値
     */
    Result solve() {
        assert(!solved_);
        solved_ = true;

        ll flow = graph_.flow(source_, sink_);

        /*
         * max-flow 後、source から残余グラフで到達可能な頂点が
         * min-cut の S 側。
         */
        std::vector<bool> side = graph_.min_cut(source_);

        std::vector<int> values(n_, 0);

        for (int var = 0; var < n_; ++var) {
            /*
             * S 側の threshold 頂点が
             *
             *   1, 2, ..., x
             *
             * になるので、その最大値が x。
             */
            for (int p = 1; p < k_; ++p) {
                if (side[vertex_id(var, p)]) {
                    values[var] = p;
                }
            }
        }

        return {
            offset_ + flow,
            std::move(values)
        };
    }
};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	int n,m;
	cin>>n>>m;
	vl a(n),b(n);
	input_vec(a,b);
	MongeMinCut f(n,2);
	ll ans=0;
	for(int i=0;i<n;i++){
		f.add_unary_cost(i,{-b[i],-a[i]});
	}
	while(m--){
		int u,v;
		ll c;
		cin>>u>>v>>c;
		u--;v--;
		f.add_pairwise_cost(u,v,{{0,c},{c,0}});
	}
	cout<<-f.solve().cost<<endl;
}