并查集、分析

题意：

Problem Description
There are n cities and m bidirectional roads in Byteland. These cities are labeled by 1,2,…,n, the brightness of the i-th city is bi.

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 k (1≤k≤n).

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

· For every selected city ci (1≤i≤k), decrease bci by 1.

Note that Sunset will always choose k 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 T (1≤T≤10), the number of test cases.

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

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

Each of the following m lines contains two integers ui and vi (1≤ui,vi≤n,ui≠vi), denoting an bidirectional road between the ui-th city and the vi-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

分析

我们以样例为例，会发现在最开始我们对连通块1-2-3进行减一操作，
直到2号节点变为0然后我们再分别对1号,3号节点进行减一操作，使其变为零。一共4步。
那么我们就发现这题的关键了对于联通块A，其中最小的元素所在的节点为a
那么我们最多对连通块实行减一的操作直到节点a等于0，在这之后便不能再次实行了。
然后将与a相连的边全部断开，再次划分连通块，然后重复操作。。。。。。
这是十分麻烦且困难的，我们每次断开后都要重新找连通块，进行遍历耗时太长。O(n^2)

必须采取别的方法：
我们注意到实行减一的时候我们实际上只是受到权值最小的那个节点的制约。
倘若我们在在对连通块A进行总体减一之前我们先将所有的节点都尝试减到a的程度呢？
这是我们的想法。逆向思维。
我们把节点统统按照权值排序，如[4,3,2]
然后我们从栈顶拿元素4看他和下一个栈顶元素的差值1，那么我们减一将他变成3
然后我们再从栈顶拿元素3，发现他和已经拿的元素有边，那他们链接成为一个连通块。
我们接下来只要对这个连通块减一，变为2就好了。
倘若，没有相连的边，那么我们实际上就有两个连通块，对了这两个都实行减一操作将其 变为2.操作数+2
。。。。。。。。
如此继续下去我们最终将会得到答案。
绝妙的逆向思维

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>;
using namespace std;
typedef long long ll;
const int max_n = 1e5 + 100;
struct node
{
    ll val;
    int num;
    int id;
    vector<int> son;
    bool operator<(const node& n1) { return val > n1.val; }
}N[max_n];
int idx[max_n];


int par[max_n];
int rak[max_n];
void init(int n) {
    for (int i = 0;i < n;i++) {
        par[i] = i;
        rak[i] = 0;
    }
}

int find(int x) {
    if (par[x] == x)return x;
    return par[x] = find(par[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y)return;
    if (rak[x] < rak[y])par[x] = y;
    else {
        par[y] = x;
        if (rak[x] == rak[y])rak[x]++;
    }
}


int main() {
    ios::sync_with_stdio(0);
    int t;cin >> t;
    while (t--) {
        int n, m;cin >> n >> m;
        init(n + 1);for (int i = 1;i <= n;i++)N[i].son.clear();
        for (int i = 1;i <= n;i++) cin >> N[i].val, N[i].id = i;
        sort(N + 1, N + 1 + n);
        for (int i = 1;i <= n;i++) N[i].num = i, idx[N[i].id] = N[i].num;
        for (int i = 1;i <= m;i++) {
            int u, v;cin >> u >> v;
            u = idx[u];v = idx[v];
            if (u > v)N[u].son.push_back(v);
            else N[v].son.push_back(u);
        }
        ll count_set = 0;
        ll ans = 0;
        ll before = N[1].val;
        for (int i = 1;i <= n;i++) {
            node& nn = N[i];
            set<int> quchong;
            for (int j = 0;j < nn.son.size();j++) {
                quchong.insert(find(nn.son[j]));
                unite(nn.son[j], nn.num);
            }
            ans += count_set * (before - nn.val);
            before = nn.val;
            count_set = count_set - quchong.size() + 1;
        }
        ans += (count_set)*before;
        cout << ans << endl;
    }
}

注意，我们拿走栈顶元素后判断他和已知的连通块有无边，是通过并查集实现的。另外，在遍历边时要忽略通往权值比他小的顶点的边。即，输入时要进行筛选