[ABC267E] Erasing Vertices 2 Solution

• [ABC267E] Erasing Vertices 2 Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

给定 $ 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 初稿