ABC267E
最大値の最小化は, binary search が典型． しかし，解法から攻めるのは王道とは言えない． まずは性質を考える．
単調性 \(\cdots (*)\)
取り除く作業を繰り返してく． ある時点でコスト \(y\) 以下の vertex は，それ以降もずっと コストが \(y\) 以下，という単調性がある． この単調性に基づいて binary search を行う．
貪欲\(\cdots (**)\)
先ほどの単調性から，除いてよい vertex は先に取り除いても損をしない． このことから，コストの小さい順に貪欲に削除出来そうである．
解法0: Binary search, 単調性
\(x \in Codom(Cost)\) を固定する． (コスト \(x\) 以下となる取り除き方が存在する) \(\in Bool\) は単調性がある．
true になることは， ある取り除き方が存在して， 取り除くすべてのタイミング \(i \in N\) に対して (\(i\) のコスト ) \(\leq x\) となることと同値．
また，単調性 \((*)\) より，(\(i\) のコスト) \(\leq x\) となる 頂点 \(i\) は，すぐに取り除いてよいので， queue に入れておく．
空間計算量は \( O (N+M) \)， 時間計算量は \( O ( (N+M) log\, K) \)． ここで，\(K\) は最大ケースのコスト．
解法1: Priority queue, 貪欲
貪欲 \((**)\) より，コストが小さい頂点から貪欲に消していく 最前手が存在する．
実装コードでは， 余分に priority queue に pair が入っているが， コストが低いほうが優先される． よって，コストの大きいほうは使われないでアルゴリズムが完了する．
空間計算量は \( O (N+M) \)， 時間計算量は \( O ( (N+M) log\, (N+M) )\)．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
// binary search
int main() {
ll n, m ;
cin >> n >> m;
vll v(n); rep(i,n) { cin >> v[i]; }
rep(i,m){
ll a,b; cin >> a >> b;
--a,--b;
ed[a].emplace_back(b,i); // index of edge は不要
ed[b].emplace_back(a,i);
}
ll ok, ng;
ok = 1e18, ng = -1;
while(abs(ok-ng) > 1){
ll md = (ok + ng)/2;
vll cost(n);
rep(a,n){
for(auto [b,i]: ed[a]){
cost[a] += v[b];
}
}
queue<ll> q;
rep(i,n){
if(cost[i] <= md) q.push(i);
}
// vector<bool> r_e(m); // removed edge
vector<bool> r_v(n); // removed vertex
while(q.size()){
ll cu = q.front(); q.pop();
if(r_v[cu]) continue;
r_v[cu] = true;
for(auto [ne, i]: ed[cu]) if(!r_v[ne]) { // if(!r_e[i])
cost[ne] -= v[cu];
// r_e[i] = true;
if(cost[ne] <= md) q.push(ne);
}
}
bool f = true;
rep(i,n) if(!r_v[i]) f = false;
if(f) ok = md;
else ng = md;
}
cout << ok << endl;
return 0;
}
// min priority queue
int main() {
ll n, m ;
cin >> n >> m;
vll v(n); rep(i,n) { cin >> v[i]; }
vll cost(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a,--b;
ed[a].emplace_back(b);
ed[b].emplace_back(a);
cost[a] += v[b];
cost[b] += v[a];
}
min_priority_queue<pll> q;
rep(i,n) q.push({cost[i],i});
ll ans = -INFL;
while(q.size()){
auto [co, vi] = q.top(); q.pop();
if(r_v[vi]) continue;
r_v[vi] = true;
ll s = 0;
for(auto nvi: ed[vi]) if(!r_v[nvi]){
s += v[nvi];
cost[nvi] -= v[vi];
q.push({cost[nvi], nvi});
}
chmax(ans, s);
}
rep(i,n) if(!r_v[i]) assert(false);
cout << ans << endl;
return 0;
}
