ABC267 E - Erasing Vertices 2

今天药忘吃喽~ 2024-03-24 15:46 55阅读 0赞

**一道DS好题！**

题意：

![804c8068f63a4b76865017f1a62cf33c.png][]

![dea11b8712d1472f83cdb1cf7198ca65.png][]

思路：

**图论的题，一般都是从特殊条件入手**

考虑它的操作，删除一个点，点周围所有点的权值都减去a\[u\]

我们要使最大值最小

那么思路肯定是从贪心入手

注意到，如果我们先删大的，那么最大值就定格在那里了

但是如果先删比较小的，大的那个点可能就变小了，贡献也就可能变小

因此可以猜测贪心策略可能是：先删小的再删大的

证明的话就是反证法，先删大的点的贡献一定不小于先删小的

那么我们从小到大删，然后去维护最大值

还有个问题就在于怎么去动态维护最大值

对于动态维护一个东西，肯定就是DS没跑了

DS一般怎么去考虑呢？就是先去考虑我们要维护的是什么东西，然后再去考虑修改操作对需要维护的东西的影响

我们要维护最大值，删去一个点之后，周围所有点的权值都减去中间那个点的权值，这对全局最大值的影响不能直接维护

那就是去考虑线段树了，考虑动态维护一个序列就行，删去一个点之后，修改特定编号的权值，那就是单点修改了，然后**维护的就是全局的最小值**了，然后还要**维护哪个点是最小值**，因为贪心策略

这就是DS的含金量！

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=998244353;
    const int Inf=1e18;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    struct Tree{
        int val,pos;
    }tree[mxe<<2];
    
    int n,m,u,v,tot=0;
    int a[mxn],head[mxn],w[mxn],del[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void pushup(int rt){
        tree[rt].val=min(tree[rt<<1].val,tree[rt<<1|1].val);
        if(tree[rt].val==tree[rt<<1].val) tree[rt].pos=tree[rt<<1].pos;
        if(tree[rt].val==tree[rt<<1|1].val) tree[rt].pos=tree[rt<<1|1].pos;
    }
    void build(int rt,int l,int r){
        if(l==r){
            tree[rt].val=w[l];
            tree[rt].pos=l;
            return;
        }
        int mid=l+r>>1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        pushup(rt);
    }
    void modify(int rt,int l,int r,int x,int k){
        if(l==r){
            tree[rt].val+=k;
            return;
        }
        int mid=l+r>>1;
        if(x<=mid) modify(rt<<1,l,mid,x,k);
        else modify(rt<<1|1,mid+1,r,x,k);
        pushup(rt);
    }
    void solve(){
        cin>>n>>m;
        G_init();
        for(int i=1;i<=n;i++) cin>>a[i];
        while(m--){
            cin>>u>>v;
            add(u,v);
            add(v,u);
            w[u]+=a[v];
            w[v]+=a[u];
        }
        build(1,1,n);
        int ans=0;
        for(int i=1;i<=n;i++){
            ans=max(ans,tree[1].val);
            int pos=tree[1].pos;
            del[pos]=1;
            for(int i=head[pos];~i;i=edge[i].next){
                if(!del[edge[i].to]){
                    modify(1,1,n,edge[i].to,-a[pos]);
                }
            }
            modify(1,1,n,pos,Inf);
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[804c8068f63a4b76865017f1a62cf33c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/fceaca478aba412db249917746d489f3.png
[dea11b8712d1472f83cdb1cf7198ca65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/53b7d37ef9ba42ccb78fb22f482f2efc.png