Atcoder 题解

Atcoder Beginner Contest 267 problem E 题解

题目链接:点我

题目大意

给定一张$N$点$M$边的简单无向图，每个点有一个点权$w_i$。进行$N$次操作，每次操作会删除一个点，删除一个点的代价是:这个点的所邻点的点权和。然后对于后续操作，这个点与连接到这个点的所有边都不复存在。问$N$次操作中，单次代价的最大值最小可以是多少？

样例输入1

4 3
3 1 4 2
1 2
1 3
4 1

样例输出1

3

样例解释1

通过如下$4$次操作，我们可以得到最小的最大值$3$：

• 删除点$3$。代价是$w_1 = 3$。
• 删除点$1$。代价是$w_2 + w_4 =3$。
• 删除点$2$。代价是$0$。
• 删除点$4$。代价是$0$。

可以证明，没有一个方案得到的最大值比$3$更小。

样例输入2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

样例输出2

1199

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq W_i \leq 10^9$
• $1 \leq U_i,V_i \leq N$
• 所有读入均为整型数。

解析

求最大值最小，二分？？

其实，这道题是一道贪心。我们仔细想想，我们要找到最小的最大值，那么我们在每次删点操作时，肯定是更贪心的选择所有未删的点中花费代价最少的点。

所以，每次操作只要找到所有点中花费代价最少的点即可。

但是怎么找呢？双层枚举，$O(N^2)$ ？肯定会炸。因此，我们必须来找一些优化的技巧。

对于快速找到最小值，且可以插入删除指定元素的容器，你们想到了什么？没错，那就是$set$。

在读入时，我们就可以处理出删除一个点所需要花费的代价。

我们把所有未删的点都插入$set$容器中，那么每次删点操作直接取第一个元素即可。因为$set$内部已经按照从小到大排好了序。

那么删点之后如何更新呢？

我们可以枚举这个点的所有邻点，然后这些邻点的原有代价减去这个点的点权即可。因为这个点被删除，那么它的邻点被删除时，所需要计算的点会少了当前这一个点。(如果不好理解，可以看代码并画图模拟一下。)

总时间复杂度$O((N+M) \log N)$。

代码实现

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
#define int long long
const int N=4e5+5;
typedef pair<int,int> pii;
int n,m,val[N],ans;
int he[N],ne[N],go[N],tot;
set<pii> s;//存储未删除的点。因为我们需要知道当前删除的点的编号，因此采用pair将代价与编号捆绑起来。
int deg[N]; //deg[i]表示删除i号点所需要的代价。
bool vis[N]; //这里有一个小细节：我们在删一个点，枚举其邻点时，必须要判断这个点是否已经被删除。否则会WA得不知所措(悲
inline void add(int a,int b){
    ne[++tot]=he[a];he[a]=tot;go[tot]=b;
}//前向星建图
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>val[i];
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
        deg[u]+=val[v];deg[v]+=val[u]; //处理deg数组
    }
    for(int i=1;i<=n;i++) s.insert({deg[i],i}); //开始所有的点都未被删除
    for(int i=1;i<=n;i++){
        auto t=s.begin();s.erase(t); //取set首元素并删除
        pii res=*t;//迭代器转pii
        vis[res.second]=1;//标记该点已被删除
        ans=max(ans,deg[res.second]);//用删去这个点所需要的代价更新答案
        for(int j=he[res.second];j;j=ne[j]){
            int v=go[j]; //枚举邻点
            if(vis[v]) continue; //如果这个点已经被删除，则跳过
            s.erase({deg[v],v}); //取出编号为v的这个点
            deg[v]-=val[res.second]; //更新删去这个点所需要的的代价
            s.insert({deg[v],v}); //放回这个点
        }
        //set会自动排序，以便下一次删点。
    }
    cout<<ans;
}

一定要判断是否被删去！！！血的教训

完结撒花~~~