結果
| 問題 | No.3699 引き抜き交渉 |
| コンテスト | |
| ユーザー |
 edon8618
|
| 提出日時 | 2026-09-09 21:27:20 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 2 ms / 2,000 ms |
| + 815µs | |
| コード長 | 14,358 bytes |
| 記録 | |
| コンパイル時間 | 4,298 ms |
| コンパイル使用メモリ | 381,580 KB |
| 実行使用メモリ | 6,528 KB |
| 最終ジャッジ日時 | 2026-09-09 21:27:36 |
| 合計ジャッジ時間 | 6,114 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
ソースコード
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
#define ll long long
#define ld long double
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
template<class T, class U>
inline bool chmax(T &a, const U &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class T, class U>
inline bool chmin(T &a, const U &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
// #define ll int
// #define ll int128_t
// #define ll int256_t
// #define ll cpp_int
constexpr ll inf = (1ll << 62);
// constexpr ll inf = (1 << 30);
// const double PI=3.1415926535897932384626433832795028841971;
uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123;
inline uint32_t xor_next() {
uint32_t t = xor_x ^ (xor_x << 11);
xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8));
}
inline int rnd(int max_val) { return xor_next() % max_val; }
struct Timer {
std::chrono::steady_clock::time_point start_time;
Timer() {
reset();
}
// 測定の起点リセット用
void reset() {
start_time = std::chrono::steady_clock::now();
}
// スタートからの経過時間をミリ秒(msec)で返す
long long get_ms() const {
auto now = std::chrono::steady_clock::now();
return std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time).count();
}
};
// ll rui(ll a,ll b){
// if(b==0)return 1;
// if(b%2==1) return a*rui(a*a,b/2);
// return rui(a*a,b/2);
// }
// vl fact;
// ll kai(ll n){
// fact.resize(n,1);
// rep(i,n-1)fact[i+1]=fact[i]*(i+1);
// }
// using mint = ld;
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = static_modint<922267487>; // 多分落とされにくい NOT ntt-friendly
// using mint = static_modint<469762049>; // ntt-friendly
// using mint = static_modint<167772161>; // ntt-friendly
// using mint = modint;//mint::set_mod(mod);
// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
// a%=mod;
// if(b==0)return 1;
// if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
// return modrui(a*a%mod,b/2,mod)%mod;
// }
// void incr(vl &v,ll n){// n進法
// ll k=v.size();
// v[k-1]++;
// ll now=k-1;
// while (v[now]>=n)
// {
// v[now]=0;
// if(now==0)break;
// v[now-1]++;
// now--;
// }
// return;
// }
// vector<mint> fact,invf;
// void init_modfact(ll sz){
// fact.resize(sz);
// invf.resize(sz);
// fact[0]=1;
// rep(i,sz-1){
// fact[i+1]=fact[i]*(i+1);
// }
// invf[sz-1]=1/fact[sz-1];
// for(ll i=sz-2; i>=0; i--){
// invf[i]=invf[i+1]*(i+1);
// }
// }
// mint choose(ll n,ll r){
// if(n<r || r<0 || n<0)return 0;
// return fact[n]*invf[r]*invf[n-r];
// }
// vector<mint> modpow,invpow;
// void init_modpow(ll x,ll sz){
// mint inv=1/mint(x);
// modpow.assign(sz,1);
// invpow.assign(sz,1);
// rep(i,sz-1){
// modpow[i+1]=modpow[i]*x;
// invpow[i+1]=invpow[i]*inv;
// }
// }
// long long phi(long long n) {// O(sqrt(n))
// long long res = n;
// for (long long i = 2; i * i <= n; i++) {
// if (n % i == 0) {
// res -= res / i;
// while (n % i == 0) n /= i;
// }
// }
// if (n > 1) res -= res / n;
// return res;
// }
/**https://atcoder.jp/contests/abc326/submissions/76493824
* @brief 燃やす埋める (Project Selection Problem)
* * 最小カット（最大流）を用いて、N個の変数を 0 (S側) か 1 (T側) のどちらかに
* 割り当て、以下の目的関数の総和を最小化するアルゴリズムです。
* * [最小化する目的関数]
* Σ (頂点 v を 0 にしたときの基本コスト)
* + Σ (頂点 v を 1 にしたときの基本コスト)
* + Σ (頂点 u を 0, 頂点 v を 1 にしたときのペナルティ)
* + Σ (u, v の 2 変数に対する劣モジュラなコスト行列)
* * [S側とT側の直感的な意味]
* - 0 (S側): グラフのカット後、Source(始点)側と繋がっている状態。
* 例: 「燃やす」「選ばない」「条件を満たさない」
* - 1 (T側): グラフのカット後、Sink(終点)側と繋がっている状態。
* 例: 「埋める」「選ぶ」「条件を満たす」
* * ※ 注意事項
* - ペナルティの重みは必ず非負 (w >= 0) である必要があります。
* - add_pair に渡すコスト行列は、劣モジュラ不等式 $C_{00} + C_{11} \le C_{01} + C_{10}$
* を満たす必要があります（揃えた方がコストが安い、あるいはペナルティが少ない状態）。
* - マイナスのコスト（報酬）が絡む場合は、内部でオフセットを加算し、
* 自動で正の容量を持つグラフに変換処理されます。
*/
template <class Cap>
struct ProjectSelection {
int n;
int S, T;
mf_graph<Cap> graph;
Cap offset_cost;
ProjectSelection() : n(0), S(0), T(0), offset_cost(0) {}
// 頂点数 n で初期化。S=n, T=n+1 として構築。
ProjectSelection(int n) : n(n), S(n), T(n + 1), graph(n + 2), offset_cost(0) {}
/**
* @brief 頂点の基本コストを追加
* @param v 対象の頂点 (0-indexed)
* @param c0 0 (S側・燃やす) にしたときにかかるコスト
* @param c1 1 (T側・埋める) にしたときにかかるコスト
*/
void add_node(int v, Cap c0, Cap c1) {
assert(0 <= v && v < n);
if (c0 < c1) {
graph.add_edge(S, v, c1 - c0); // 1にするための追加ペナルティ
offset_cost += c0; // どちらにせよ最低限 c0 はかかる
} else {
graph.add_edge(v, T, c0 - c1); // 0にするための追加ペナルティ
offset_cost += c1; // どちらにせよ最低限 c1 はかかる
}
}
/**
* @brief 0-1パターンのペナルティを追加
* @param u 0 (S側) になる頂点
* @param v 1 (T側) になる頂点
* @param w ペナルティのコスト (w >= 0)
*/
void add_penalty_01(int u, int v, Cap w) {
assert(0 <= u && u < n && 0 <= v && v < n);
assert(w >= 0);
graph.add_edge(u, v, w);
}
/**
* @brief 1-0パターンのペナルティを追加
*/
void add_penalty_10(int u, int v, Cap w) {
add_penalty_01(v, u, w);
}
/**
* @brief 2変数のコスト行列をそのまま追加 (最強メソッド)
* @details c00 + c11 <= c01 + c10 (劣モジュラ性) を満たす必要がある
*/
void add_pair(int u, int v, Cap c00, Cap c01, Cap c10, Cap c11) {
assert(c00 + c11 <= c01 + c10); // 劣モジュラ性の確認
offset_cost += c00;
add_node(u, 0, c10 - c00);
add_node(v, 0, c11 - c10);
add_penalty_01(u, v, c01 + c10 - c00 - c11);
}
/**
* @brief 最小コストを計算
*/
Cap solve() {
return graph.flow(S, T) + offset_cost;
}
/**
* @brief 最小コスト達成時の割り当てを復元
* @return vector<int> 各頂点が 0(S側) か 1(T側) かの配列
*/
vector<int> get_assignment() {
vector<bool> cut = graph.min_cut(S);
vector<int> res(n);
for (int i = 0; i < n; ++i) {
res[i] = cut[i] ? 0 : 1;
}
return res;
}
};
/**https://atcoder.jp/contests/abc347/submissions/76575746
* @brief 多値の燃やす埋める (Multi-choice Project Selection)
* * N個の変数がそれぞれ 0 ~ K-1 のいずれかの値をとる場合のコスト最小化を行います。
* 内部で 2値の ProjectSelection を呼び出し、「変数 i の値は k 以上か？」という
* YES(1)/NO(0) の二値グラフに自動で帰着させて解きます。
* * [最小化する目的関数]
* Σ (変数 u を値 x にしたときの個別コスト C[u][x])
* + Σ (変数 u を値 x、変数 v を値 y にしたときのペアコスト M[x][y])
* * [必須制約: Monge性]
* add_binary_cost に渡すコスト行列 M は、必ず Monge性 を満たす必要があります。
* 数式: M[i][j] + M[i-1][j-1] <= M[i-1][j] + M[i][j-1]
* 直感的な意味: 差の絶対値 |x-y| や差の二乗 (x-y)^2 のように、
* 「値の差が広がるほどペナルティが大きくなる（凸関数）」コスト行列であれば解けます。
* * @par 使用例
* @code
* // N=3 の変数がそれぞれ 0~4 (5択) の値をとる場合
* ProjectSelectionMulti<ll> psp({5, 5, 5});
* * // 1変数の個別コストを追加
* vector<ll> c0 = {10, 5, 8, 2, 0}; // 0を選ぶと10、1を選ぶと5...
* psp.add_unary_cost(0, c0);
* * // 2変数間のペアコストを追加 (5x5のMonge行列 M を投げる)
* psp.add_binary_cost(0, 1, M);
* * // 最小コストの計算と、各変数が 0~4 のどれになったかの復元
* ll min_cost = psp.solve();
* vector<int> res = psp.get_assignment();
* @endcode
*/
template <class Cap>
struct ProjectSelectionMulti {
int n;
vector<int> K;
vector<int> start_idx;
ProjectSelection<Cap> psp;
Cap INF_CAP;
/**
* @brief 初期化
* @param K_ 各変数の選択肢の数 (例: 全マス 5 択なら vector<int>(N, 5))
* @param inf_cap 絶対に選ばれないための無限大コスト (1e15 など)
*/
ProjectSelectionMulti(const vector<int>& K_, Cap inf_cap = 1e15)
: n(K_.size()), K(K_), INF_CAP(inf_cap) {
int total_vars = 0;
start_idx.assign(n, 0);
for(int i = 0; i < n; ++i) {
start_idx[i] = total_vars;
total_vars += max(0, K[i] - 1);
}
psp = ProjectSelection<Cap>(total_vars);
// 状態の矛盾を防ぐための ∞ 辺 (例: 「3以上」がYESなのに「2以上」がNOになるのはあり得ない)
for(int i = 0; i < n; ++i) {
for(int k = 1; k < K[i] - 1; ++k) {
// psp.add_penalty_01( 0(NO)になる頂点, 1(YES)になる頂点, 罰金 );
psp.add_penalty_01(idx(i, k), idx(i, k + 1), INF_CAP);
}
}
}
// 内部変数マッピング (変数 i が k 以上か？ を表す 2値ノードのインデックス)
int idx(int i, int k) {
assert(0 < k && k < K[i]);
return start_idx[i] + k - 1;
}
/**
* @brief 1変数の個別コストを追加
* @param u 対象の変数
* @param C 大きさ K[u] のコスト配列 (C[x] は 変数 u を x にした時のコスト)
*/
void add_unary_cost(int u, const vector<Cap>& C) {
assert((int)C.size() == K[u]);
psp.offset_cost += C[0];
for(int x = 1; x < K[u]; ++x) {
// 前の選択肢との「差分」を 2値ライブラリの add_node に投げる魔法
psp.add_node(idx(u, x), 0, C[x] - C[x - 1]);
}
}
/**
* @brief 2変数間のペアコストを追加 (Monge行列であること)
* @param u, v 対象の変数
* @param M 大きさ K[u] × K[v] のコスト行列
*/
void add_binary_cost(int u, int v, const vector<vector<Cap>>& M) {
assert((int)M.size() == K[u] && (int)M[0].size() == K[v]);
psp.offset_cost += M[0][0];
for(int i = 1; i < K[u]; ++i) psp.add_node(idx(u, i), 0, M[i][0] - M[i - 1][0]);
for(int j = 1; j < K[v]; ++j) psp.add_node(idx(v, j), 0, M[0][j] - M[0][j - 1]);
for(int i = 1; i < K[u]; ++i) {
for(int j = 1; j < K[v]; ++j) {
// 2x2部分の Monge 性を判定し、負の報酬を 1-1 ペアに付与する魔法
Cap delta = M[i][j] - M[i - 1][j] - M[i][j - 1] + M[i - 1][j - 1];
if (delta < 0) {
psp.add_pair(idx(u, i), idx(v, j), 0, 0, 0, delta);
} else {
assert(delta <= 0 && "Matrix must be Monge!");
}
}
}
}
Cap solve() {
return psp.solve();
}
/**
* @brief 最小コスト達成時の割り当てを復元
* @return vector<int> 各変数が 0 ~ K[i]-1 のどれに割り当てられたかの配列
*/
vector<int> get_assignment() {
// 内部の2値ライブラリの割り当て結果 (0 or 1) を取得
vector<int> bin_res = psp.get_assignment();
vector<int> ans(n, 0);
for (int i = 0; i < n; ++i) {
int val = 0;
// その変数に属する閾値ノード (k = 1 ~ K[i]-1) を調べる
for (int k = 1; k < K[i]; ++k) {
if (bin_res[idx(i, k)] == 1) {
val++; // 1 (T側) になっているノードの数を数える
}
}
ans[i] = val;
}
return ans;
}
};
void solve(){
ll n,m;
cin >> n >> m;
vl a(n),b(n);
rep(i,n)cin >>a[i] >> b[i];
ProjectSelection<ll> psp(n);
rep(i,n){
psp.add_node(i,-a[i],-b[i]);
}
rep(i,m){
ll u,v,c;
cin >> u >> v >> c;
u--;
v--;
psp.add_penalty_01(u,v,c);
psp.add_penalty_01(v,u,c);
}
cout << -psp.solve() << endl;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
// ll mx=12345678;
// vc fl(mx+1,0);
// for(ll d=2;d<=mx;d++){
// if(fl[d])continue;
// ll x=d;
// ps.push_back(x);
// while(x<=mx){
// fl[x]=1;
// x+=d;
// }
// }
ll t = 1;
// cin >> t;
while (t--){
solve();
}
}