给定
第一眼看完以为是维护删除能节省的对于其它点的花费(即点权乘度数)减去删除的花费,每次删去最大的并动态维护相连点的该值,可以用平衡树维护,当然假了,因为后来才发现最小化的不是花费和,而是最大值。
然后想到的是每次删花费最大的点相连的花费最小的点,即想办法降低最大点的最大值,并动态维护,当然也可以用平衡树,不过这个东西仔细想一下就发现假了,最大点连结的最小点或许可能可以通过最小点连结的次小点更新,以此类推,如果一直找到最小没有分析,不过复杂度基本上是完全不可接受的。
于是在浪费了不少时间后我才想到了这个十分显然的正解,即显然我们直接删除花费最小的即可。因为如果你删除其它的任意点一定会使最大花费变大,那么这个点一定可以被删除且不贡献花费。于是我们每次找到花费最小的点,并动态维护相连其它点的花费即可。这个过程我使用了平衡树维护,即支持插入,删除,找第
另外此题仍然存在思路,即二分答案,然后
Tips:后来被机房同学提醒了一下之后我才愕然发现这东西用不到平衡树,直接正常维护优先队列,记录一下
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)
等操作。
xxxxxxxxxx
811
2
3
4
5
6
7
8
9
10
11
12using namespace std;
13using namespace __gnu_pbds;
14
15mt19937 rnd(random_device{}());
16int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17bool rnddd(int x){return rndd(1, 100) <= x;}
18
19typedef unsigned int uint;
20typedef unsigned long long unll;
21typedef long long ll;
22typedef long double ld;
23
24template < typename T = int >
25inline T read(void);
26
27int N, M;
28ll A[210000];
29ll cost[210000];
30ll ans(LONG_LONG_MIN);
31bitset < 210000 > vis;
32
33struct Edge{
34 Edge* nxt;
35 int to;
36 OPNEW;
37}ed[410000];
38ROPNEW;
39Edge* head[210000];
40
41tree < pair < ll, int >, null_type, less < pair < ll, int > >, rb_tree_tag, tree_order_statistics_node_update > tr;
42
43int 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
67template < typename T >
68inline 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}
update-2023_01_14 初稿