2022牛客寒假算法基础集训营2 B.小沙的魔法 并查集

概述

n n n个点 m m m条边的图上，每个点的初始权值为 0 0 0。给定一个边集，每次可以进行两种操作：

1. 在 m m m条边里选择一条边加入图中；
2. 将图上某一连通块的所有点权 + 1 +1 +1.

求最小操作数，使得图上点权 x i = a i x_i = a_i xi​=ai​。

首先考虑如何减少操作数：也就是如何减少无意义的分次加点权。如果对于两个点权 a , b ( a > b ) a, b(a > b) a,b(a>b)，显然我们可以将一个点的点权增加至 ( a − b ) (a - b) (a−b)，然后将两个点合并起来加点权，这样可以刚好将两个点权初始为 0 0 0的点变为权值为 a , b a,b a,b的两个点。

按照以上思路，我们可以"反向操作"，即先统计最朴素的操作次数(权值和)，然后按照权值大小对点进行排序，然后依次遍历每个点的邻接表，对权值大于等于当前点的连通块进行合并。最后得出的操作数即为最小操作数。

Accepted Code

#include 
#define int long long
using namespace std;

const int N = 5e5 + 10;
int fa[N], q[N];

vector g[N];

struct node{ int id, val; }a[N];

const static inline bool cmp(const node &aa, const node &bb){ return aa.val > bb.val; }

inline int Find(int x){ return x == fa[x] ? x : fa[x] = Find(fa[x]); }

inline void solve(){
    int n, m, res = 0; cin >> n >> m;
    for(int i = 1; i > a[i].val;
    for(int i = 1; i  u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    for(int i = 1; i  q[v] || u == v) continue;
            //cout