題意：$n$個(gè)點(diǎn)$m$條邊的無向圖，每個(gè)點(diǎn)有一個(gè)正點(diǎn)權(quán)，每次選擇一個(gè)連通子圖，將里面的權(quán)值都減$1$。求所有點(diǎn)權(quán)為$0$的最小步數(shù)。

$T\le 10,n\le 10^5,m\le 2\times 10^5$

考慮一個(gè)貪心：每次一定選擇一個(gè)極大的連通塊。

感性理解很容易，還是證明一下：

假設(shè)一個(gè)極大連通塊$S$，我偏不選，只選擇它的子連通塊來覆蓋整個(gè)$S$，答案嚴(yán)格更優(yōu)。考慮兩個(gè)連在一起的連通塊$T_1,T_2$，選擇$T_1\cup T_2,T_1\cap T_2$一定不比選$T_1,T_2$劣。因?yàn)檫x擇的連通塊覆蓋了整個(gè)$S$，所以可以一步步合并出$S$（即任選一個(gè)與當(dāng)前集合相鄰的點(diǎn)，將覆蓋它的集合與當(dāng)前集合合并），答案不會(huì)更劣，矛盾。

對(duì)于一個(gè)連通塊來說，一定是點(diǎn)按照權(quán)值從小到大被刪。把操作順序倒過來，就是把大的結(jié)點(diǎn)減小成和小的結(jié)點(diǎn)相同，然后一起刪掉。

形式化地講，就是把權(quán)值從大到小排序依次加入，并把全場的權(quán)值都減到當(dāng)前權(quán)值。用并查集維護(hù)連通塊個(gè)數(shù)即可。

復(fù)雜度$O(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <vector> #define MAXN 100005 using namespace std; typedef long long ll; vector<int> e[MAXN]; int fa[MAXN]; inline int find(const int& x){return fa[x]==x? x:fa[x]=find(fa[x]);} int a[MAXN],p[MAXN],vis[MAXN]; inline bool cmp(const int& x,const int& y){return a[x]>a[y];} int main() {int T;scanf("%d",&T);while (T--){int n,m;scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) e[i].clear(),fa[i]=p[i]=i,vis[i]=0,scanf("%d",&a[i]);for (int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);e[u].push_back(v),e[v].push_back(u);}sort(p+1,p+n+1,cmp);int cur=1;ll ans=0;vis[p[1]]=1;for (int i=2;i<=n;i++){ans+=(ll)cur*(a[p[i-1]]-a[p[i]]);++cur;for (vector<int>::iterator it=e[p[i]].begin();it!=e[p[i]].end();++it){int u=p[i],v=*it;if (!vis[v]) continue;u=find(u),v=find(v);if (u!=v) fa[u]=v,--cur;}vis[p[i]]=1;}ans+=(ll)cur*a[p[n]];printf("%lld\n",ans);}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【杭电多校2020】Total Eclipse【贪心】【并查集】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。