[ABC267E] Erasing Vertices 2 Solution
目录更好的阅读体验戳此进入
题面
给定 $ n $ 个点 $ m $ 条边的无向图,给定点权,每次可以删除一个点,定义其花费为与其相连的所有没被删除的点的点权和,你需要删除所有点。最小化花费最大值,输出最小的最大值。
Solution
第一眼看完以为是维护删除能节省的对于其它点的花费(即点权乘度数)减去删除的花费,每次删去最大的并动态维护相连点的该值,可以用平衡树维护,当然假了,因为后来才发现最小化的不是花费和,而是最大值。
然后想到的是每次删花费最大的点相连的花费最小的点,即想办法降低最大点的最大值,并动态维护,当然也可以用平衡树,不过这个东西仔细想一下就发现假了,最大点连结的最小点或许可能可以通过最小点连结的次小点更新,以此类推,如果一直找到最小没有分析,不过复杂度基本上是完全不可接受的。
于是在浪费了不少时间后我才想到了这个十分显然的正解,即显然我们直接删除花费最小的即可。因为如果你删除其它的任意点一定会使最大花费变大,那么这个点一定可以被删除且不贡献花费。于是我们每次找到花费最小的点,并动态维护相连其它点的花费即可。这个过程我使用了平衡树维护,即支持插入,删除,找第 $ k $ 小(即找最小)。
另外此题仍然存在思路,即二分答案,然后 $ O(n) $ 验证即可,这个思路也不难想到。
Tips:后来被机房同学提醒了一下之后我才愕然发现这东西用不到平衡树,直接正常维护优先队列,记录一下 $ idx $ 然后不用删除,直接记录,如果 $ idx $ 对应值于优先队里里的不同那么就丢弃即可。
Tips(again):如果要使用平衡树维护的话,最普通的任意平衡树即可,因为这个用到的真的很浅,所以我们不难想到也可以直接用 __gnu_pbds::tree
维护,这里我用的是 tree < pair < ll, int >, null_type, less < pair < ll, int > >, rb_tree_tag, tree_order_statistics_node_update > tr;
,需要注意我们这里不能用默认的参数,需要手动改为 tree_order_statistics_node_update
,否则平衡树将不再支持 find_by_order(x)
以及 order_of_key(x)
等操作。
Code
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template < typename T = int >
inline T read(void);
int N, M;
ll A[210000];
ll cost[210000];
ll ans(LONG_LONG_MIN);
bitset < 210000 > vis;
struct Edge{
Edge* nxt;
int to;
OPNEW;
}ed[410000];
ROPNEW;
Edge* head[210000];
tree < pair < ll, int >, null_type, less < pair < ll, int > >, rb_tree_tag, tree_order_statistics_node_update > tr;
int main(){
N = read(), M = read();
for(int i = 1; i <= N; ++i)A[i] = read();
for(int i = 1; i <= M; ++i){
int s = read(), t = read();
head[s] = new Edge{head[s], t};
head[t] = new Edge{head[t], s};
cost[s] += A[t], cost[t] += A[s];
}make_pair(cost[1], 1);
for(int i = 1; i <= N; ++i)tr.insert({cost[i], i});
for(int c = 1; c <= N; ++c){
auto it = tr.find_by_order(0);
ans = max(ans, it->first);
vis[it->second] = true;
for(auto i = head[it->second]; i; i = i->nxt)
if(!vis[SON])
tr.erase({cost[SON], SON}),
tr.insert({cost[SON] -= A[it->second], SON});
tr.erase({it->first, it->second});
}printf("%lld\n", ans);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template < typename T >
inline T read(void){
T ret(0);
int flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2023_01_14 初稿
标签:Index,删除,int,题解,ll,Continuous,tree,花费,define From: https://www.cnblogs.com/tsawke/p/17124338.html