Total Eclipse

题目链接

题目大意

给一个无向图，有点权。
每次选一整个连通块，让这个连通块里的点权都减一，问最少操作几步可以让他们都减成0？ 减成0了就不能再减了，也就是这个点就删去了。
题意给的不明确。他没说选的连通块尽可能大。。结果到最后了改了题面说连通块必须选尽可能大的。可是，，选尽可能大的，哪来的最小操作次数。。操作次数不就是一样的吗。。这是出题人的锅

比如这个样例，如果必须选最大的连通块，那么答案是12，如果不用选最大的，答案是8。
但是后来发现这个就算是选尽可能大的连通块，我也不一定会。。
我好菜

题解

减的话，是会先把最小值减成0，然后这个点这里断开，继续选最小的。
直接减肯定会超时的。
然后 这个怎么算答案呢。
可以反过来想，然后每次先把最大的给加上，加一个点的时候，看一下直接与他相连的点有没有加进去，如果加进去了，那点权肯定比他大。直接合并，

代码:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <unordered_set>
#include <bitset>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef set<int>::iterator sit;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp2{
   bool operator()(const pii & a, const pii & b){
   return a.second < b.second;}};
int lb(int x){
   return  x & -x;}
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5+5;
int a[maxn];
std::vector<int> vv[maxn];
int vis[maxn];
int id[maxn];
int fa[maxn];
int findx(int x)
{
   
    return x == fa[x] ? x : fa[x] = findx(fa[x]);
}
bool cmp(int x,int y)
{
   
    return a[x] > a[y];
}

int per[maxn];

int main()
{
   
    int T;
    scanf("%d",&T);
    while(T -- )
    {
   
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i =1 ; i <= n; i ++ )
        {
   
            vis[i] = 0;
            vv[i].clear();
            per[i] = 0;
        }
        for (int i =1 ; i <= n; i ++ )
            scanf("%d",&a[i]);
        for (int i =1; i <= m; i ++ )
        {
   
            int x,y;
            scanf("%d%d",&x,&y);
            vv[x].pb(y);
            vv[y].pb(x);
        }
        for (int i = 1; i <= n; i ++ )
        {
   
            fa[i] = i;
            id[i] = i;
        }
        sort(id + 1,id + 1 + n,cmp);
        for (int i = 1; i <= n; i ++ )
        {
   
            int x = id[i];
            vis[x] = 1;
            for (int j = 0; j < vv[x].size(); j ++ )
            {
   
                int v = vv[x][j];
                if(vis[v] == 1)
                {
   
                    int yy = findx(v);
                    if(yy != x)
                    {
   
                        fa[yy] = x;
                        per[yy] = x;
                    }
                }
            }
        }
        ll ans = 0;
        for(int i = 1; i <= n; i ++ )
        {
   
            ans += a[i] - a[per[i]];
        }
        cout<<ans<<endl;
    }
}