HDU - 6763 Total Eclipse（并查集 + 逆向思维）

There are nn cities and mm bidirectional roads in Byteland. These cities are labeled by 1,2,…,n1,2,…,n, the brightness of the ii-th city is bibi. 

Magician Sunset wants to play a joke on Byteland by making a total eclipse such that the brightness of every city becomes zero. Sunset can do the following operations for arbitrary number of times: 

· Select an integer kk (1≤k≤n1≤k≤n). 

· Select kk distinct cities c1,c2,…,ckc1,c2,…,ck (1≤ci≤n1≤ci≤n) such that they are connected with each other. In other words, for every pair of distinct selected cities cici and cjcj (1≤i<j≤k)(1≤i<j≤k), if you are at city cici, you can reach city cjcj without visiting cities not in {c1,c2,…,ck}{c1,c2,…,ck}. 

· For every selected city cici (1≤i≤k1≤i≤k), decrease bcibci by 11. 

Note that Sunset will always choose kk with the maximum possible value. Now Sunset is wondering what is the minimum number of operations he needs to do, please write a program to help him.

Input

The first line of the input contains a single integer TT (1≤T≤101≤T≤10), the number of test cases. 

For each case, the first line of the input contains two integers nn and mm (1≤n≤1000001≤n≤100000, 1≤m≤2000001≤m≤200000), denoting the number of cities and the number of roads. 

The second line of the input contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤1091≤bi≤109), denoting the brightness of each city. 

Each of the following mm lines contains two integers uiui and vivi (1≤ui,vi≤n,ui≠vi1≤ui,vi≤n,ui≠vi), denoting an bidirectional road between the uiui-th city and the vivi-th city. Note that there may be multiple roads between the same pair of cities.

Output

For each test case, output a single line containing an integer, the minimum number of operations.

Sample Input

1
3 2
3 2 3
1 2
2 3

Sample Output

4

题意：

 n 个城市 m 条道路，每个城市都有一个亮度值，问至少需要进行多少次如下操作使得所有城市亮度值减为0。

操作是每次选择最大的一个连通图，将该连通图上所有点的亮度 - 1

思路：

应该是每次选取亮度值最小的点x，将它所在的最大连通图上所有点的亮度 - x，然后这个图就会分成两个图……

但是这样做太复杂了，

倒着想，按亮度值从大到小排序，每次选取最大的点b[i]放入图中，这个点所做的贡献就是当前图中的连通块数 * (b[i] - b[i - 1]），然后更新图的连通性，用并查集维护，遍历与当前节点相邻的所有已经在图中的节点，将他们合并，从而更新连通块数。

参考：

https://zaizai.blog.csdn.net/article/details/107554260

https://blog.csdn.net/tianyizhicheng/article/details/107543290

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 998244353;
const ll inf = 0x3f3f3f3f;

int n, m;
int b[N], fa[N];
vector<int>mp[N];
bool vis[N];

struct node {
    int id, b;
}s[N];

bool cmp(node x, node y) {
    return x.b > y.b;
}

int Find(int x) {
    if(fa[x] != x)
        fa[x] = Find(fa[x]);
    return fa[x];
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    if(xx != yy)
        fa[xx] = yy;
}

int main() {
    int t, u, v;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", &s[i].b);
            s[i].id = i;
            mp[i].clear();
            fa[i] = i;
            vis[i] = 0;
        }
        for(int i = 1; i <= m; ++i) {
            scanf("%d%d", &u, &v);
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
        sort(s + 1, s + n + 1, cmp);
        ll ans = 0, num = 1;
        vis[s[1].id] = 1;
        for(int i = 2; i <= n; ++i) {
            ans += num * (s[i - 1].b - s[i].b);
            num++;
            int siz = mp[s[i].id].size();
            for(int j = 0; j < siz; ++j) {
                u = mp[s[i].id][j];
                v = s[i].id;
                if(!vis[u]) continue;
                u = Find(u), v = Find(v);
                if(u != v) {
                    fa[u] = v;
                    num--;
                }
            }
            vis[s[i].id] = 1;
        }
        ans += num * s[n].b;
        printf("%lld\n", ans);
    }
    return 0;
}