题面

$n$ $m$ 条边的无向图，给定点权，每次可以删除一个点，定义其花费为与其相连的所有没被删除的点的点权和，你需要删除所有点。最小化花费最大值，输出最小的最大值。

Solution

第一眼看完以为是维护删除能节省的对于其它点的花费（即点权乘度数）减去删除的花费，每次删去最大的并动态维护相连点的该值，可以用平衡树维护，当然假了，因为后来才发现最小化的不是花费和，而是最大值。

然后想到的是每次删花费最大的点相连的花费最小的点，即想办法降低最大点的最大值，并动态维护，当然也可以用平衡树，不过这个东西仔细想一下就发现假了，最大点连结的最小点或许可能可以通过最小点连结的次小点更新，以此类推，如果一直找到最小没有分析，不过复杂度基本上是完全不可接受的。

$k$ 小（即找最小）。

$O(n)$ 验证即可，这个思路也不难想到。

$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


xxxxxxxxxx
81
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3
#include <bits/extc++.h>
4

5
#define PI M_PI
6
#define E M_E
7
#define npt nullptr
8
#define SON i->to
9
#define OPNEW void* operator new(size_t)
10
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
11

12
using namespace std;
13
using namespace __gnu_pbds;
14

15
mt19937 rnd(random_device{}());
16
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17
bool rnddd(int x){return rndd(1, 100) <= x;}
18

19
typedef unsigned int uint;
20
typedef unsigned long long unll;
21
typedef long long ll;
22
typedef long double ld;
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, M;
28
ll A[210000];
29
ll cost[210000];
30
ll ans(LONG_LONG_MIN);
31
bitset < 210000 > vis;
32

33
struct Edge{
34
    Edge* nxt;
35
    int to;
36
    OPNEW;
37
}ed[410000];
38
ROPNEW;
39
Edge* head[210000];
40

41
tree < pair < ll, int >, null_type, less < pair < ll, int > >, rb_tree_tag, tree_order_statistics_node_update > tr;
42

43
int main(){
44
    N = read(), M = read();
45
    for(int i = 1; i <= N; ++i)A[i] = read();
46
    for(int i = 1; i <= M; ++i){
47
        int s = read(), t = read();
48
        head[s] = new Edge{head[s], t};
49
        head[t] = new Edge{head[t], s};
50
        cost[s] += A[t], cost[t] += A[s];
51
    }make_pair(cost[1], 1);
52
    for(int i = 1; i <= N; ++i)tr.insert({cost[i], i});
53
    for(int c = 1; c <= N; ++c){
54
        auto it = tr.find_by_order(0);
55
        ans = max(ans, it->first);
56
        vis[it->second] = true;
57
        for(auto i = head[it->second]; i; i = i->nxt)
58
            if(!vis[SON])
59
                tr.erase({cost[SON], SON}),
60
                tr.insert({cost[SON] -= A[it->second], SON});
61
        tr.erase({it->first, it->second});
62
    }printf("%lld\n", ans);
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66

67
template < typename T >
68
inline T read(void){
69
    T ret(0);
70
    int flag(1);
71
    char c = getchar();
72
    while(c != '-' && !isdigit(c))c = getchar();
73
    if(c == '-')flag = -1, c = getchar();
74
    while(isdigit(c)){
75
        ret *= 10;
76
        ret += int(c - '0');
77
        c = getchar();
78
    }
79
    ret *= flag;
80
    return ret;
81
}

UPD

update-2023_01_14 初稿

[ABC267E] Erasing Vertices 2 Solution

更好的阅读体验戳此进入

题面

Solution

Code

UPD