考試不能說明所有問題，但可以說明很多問題。（受教了，~wtcl）
題意：
給一個無向圖，n個點，m條邊，每個點有有一個點權w，我們可以選擇k個互相連通的的點進行減1，問當所有點為0時，操作的最小次數。
思路：
這個題隻要按照正常思路搞其實都能把答案搞出來，隻是正常思路效率不夠。
顯然這樣的時間複雜度是，是以我們就需要避免分裂的情況，如何避免分裂，可以想想如果這個是一個有序的序列，從大到小逐漸遞減，是否就可以避免分裂成多個段，顯然是可以的。但是我們拆一個圖，圖自然會分裂成很多段，這樣我們就需要去考慮很多東西，比較麻煩。（逆向思維）我們可以構造一個和這個圖一模一樣的圖，這樣不就不會分裂。
1：有一個疑問（構造圖是否會影響結果呢）？
答：不會。按照樸素算法，我們隻需要找一個極大連通塊，算出它的答案，最後累加即可，也就是說，我們不管先算圖中的哪一極大聯通塊，最終都不會影響答案，呢我們構造圖，就會影響答案嗎？顯然不會。
2：如何構造？
答：為了不影響之後的點，我們從最大的點開始構造，首先加入最大的點，此時極大連通塊的數量為，呢麼我們要讓這個點的權值和下一個點的權值一樣時，則需要貢獻 ，然後加入這個點（下一個點），此時需要判斷有幾個極大連通塊，即判斷的關系，如果他們相連，說明他倆構成了一個極大連通塊，呢麼極大連通塊的數量減1（在沒有判斷新加入這個點前，預設這個點和其他點無關系，），并且權值向圖，貢獻值為，此時圖中所有極大連通塊的點權都為，依次往後構造，即可構造出原圖，并得到最小操作次數。
舉例：
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 5;
const ll maxn = 1e5 + 5;
struct node
{
ll v, nex;
} edge[maxn * 8];
ll cnt, head[maxn], vis[maxn];
ll pre[maxn];
void add(ll u, ll v)
{
edge[cnt].v = v, edge[cnt].nex = head[u];
head[u] = cnt++;
}
struct vain
{
ll pos, w;
} a[maxn];
bool cmp(vain x, vain y)
{
return x.w > y.w;
}
ll f(ll x)
{
if (x != pre[x])
pre[x] = f(pre[x]);
return pre[x];
}
ll join(ll x, ll y)
{
x = f(x), y = f(y);
if (x != y)
pre[x] = y;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
memset(head, -1, sizeof head);
memset(vis, 0, sizeof vis);
cnt = 0;
ll n, m;
cin >> n >> m;
for (ll i = 1; i <= n; i++)
{
pre[i] = i;
cin >> a[i].w, a[i].pos = i;
}
a[n + 1].w = 0;
sort(a + 1, a + 1 + n, cmp);
for (ll i = 0; i < m; i++)
{
ll u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
ll ans = 0, sum = 0;
for (ll i = 1; i <= n; i++)
{
ans++; //連通塊數量++
ll u = a[i].pos;
vis[u] = 1;
for (ll j = head[u]; ~j; j = edge[j].nex)
{
ll v = edge[j].v;
if (vis[v])//判斷目前點和之前已經加入的點是否會形成連通塊
{
if (f(v) != f(u))
join(u, v), ans--;
}
}
sum += ans * (a[i].w - a[i + 1].w);
}
cout << sum << endl;
}
}