牛客周赛52--E小红的图上加边(联通块)

2024/11/30 6:43:42 来源：https://blog.csdn.net/2301_80718054/article/details/140692936 浏览: 次关键词：牛客周赛52--E小红的图上加边(联通块)

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

\,\,\,\,\,\,\,\,\,\,小红有一张 nnn 个点 mmm 条边的无向图，每个节点的权值是 aia_iai。
\,\,\,\,\,\,\,\,\,\,现在小红希望加边把这个图连成连通图，每次连接的代价是新形成的联通块的最大元素值，小红想知道最小需要消耗多少代价可以把这个图连成连通的。

输入描述:

          \,\,\,\,\,\,\,\,\,\,第一行输入两个整数nnn 和 m (1≤n≤105;m\ (1 \leq n \leq 10^5;m (1≤n≤105; 0≤m≤105)0 \leq m \leq 10^5)0≤m≤105) 表示点数和边数。\,\,\,\,\,\,\,\,\,\,第二行输入 nnn 个整数 a1,a2,…,an (1≤ai≤109)a_1,a_2,\dots,a_n\ (1 \leq a_i \leq 10^9)a1,a2,…,an (1≤ai≤109) 表示每个节点的权值。\,\,\,\,\,\,\,\,\,\,接下来 mmm 行，第 iii 行输入两个整数 uiu_iui 和 vi (1≤ui,vi≤n)v_i\ (1 \leq u_i,v_i \leq n)vi (1≤ui,vi≤n) 表示无向图上第 iii 条边连接节点 uiu_iui 和 viv_ivi ，保证没有重边。

输出描述:

\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，表示最小需要消耗的代价。

示例1

输入

复制5 3 1 2 3 4 5 1 2 2 3 1 3

输出

复制9

说明

先加上 (1,4)(1, 4)(1,4) 这条边，代价是 444，然后加上 (1,5)(1, 5)(1,5) 这条边，代价是 555，总代价是 999。

做法

把每个联通块的最大值维护出来，然后最大值总和减去最小的那个即可。求连通块可以用bfs或者并查集。

1.bfs

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100010];
int vis[100010],head[100010];
long long ans;
int tot;
struct ty{int t,next;
}edge[200010];
void addedge(int x,int y){edge[++tot].t=y;edge[tot].next=head[x];head[x]=tot;
}
queue<int> q;
void bfs(int x){if(vis[x]) return ;q.push(x);while(!q.empty()){int xx=q.front();q.pop();if(vis[xx]) continue;vis[xx]=x;for(int i=head[xx];i!=-1;i=edge[i].next){if(vis[edge[i].t]) continue;q.push(edge[i].t);}}
}
int main(){memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}for(int i=1;i<=n;i++){bfs(i);}map<int,long long> mp;for(int i=1;i<=n;i++){mp[vis[i]]=max(mp[vis[i]],a[i]);}vector<long long> v;for(map<int,long long>::iterator it=mp.begin();it!=mp.end();it++){v.push_back(it->second);}sort(v.begin(),v.end());for(int i=1;i<v.size();i++) ans+=v[i];cout<<ans;
}

2.并查集

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100010];
int fa[100010];
int getfa(int x){if(fa[x]==x) return x;return fa[x]=getfa(fa[x]); 
}
void setfa(int x,int y){fa[getfa(x)]=getfa(y);
}
long long ans;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);setfa(u,v);}map<int,int> mp;for(int i=1;i<=n;i++){mp[getfa(i)]=max(mp[getfa(i)],a[i]);}vector<int> v;for(int i=1;i<=n;i++){if(getfa(i)==i) v.push_back(mp[i]);}sort(v.begin(),v.end());for(int i=1;i<v.size();i++) ans+=v[i];cout<<ans;
}