[题目通道]([ABC352E] Clique Connect - 洛谷)
鄙人今日写人生第一篇题解
希望管理大大通过
首先，我们先看题:
它说一共有n个点，m回操作。。。
每次操作 都有 一个Ki 和 Ci
Ki代表有Ki个点,Ci代表每条边所赋的边权一看就知道这是个最小生成树的板子
我使用了著名的 kruskal
话不多说贴上代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+100;//注意范围！！！
struct edge{
int u,v;
int w;
}e[N*30];//开大点儿
int fa[N],n,m,ans=0,cnt=1,x,y,a[N],t=0;//cnt计数器，记录有多少条边~
int find(int x){
if (fa[x]==x) return x;
return fa[x]=find(fa[x]);
}//找father
bool cmp(edge a,edge b){
return a.w<b.w;
}
signed main(){
std::ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);//加速
cin>>n>>m;
for (int i=1;i<=n;i++){
fa[i]=i;
}
for (int i=1;i<=m;i++){
int qq,ww;
cin>>qq>>ww;
for (int j=1;j<=qq;j++){
cin>>a[j];//临时存一遍每个点
}
for (int j=2;j<=qq;j++){//做一遍建边~
cnt++;
e[cnt].u=a[j];
e[cnt].v=a[j-1];
e[cnt].w=ww;
}
cnt++;
e[cnt].u=a[1];
e[cnt].v=a[qq];
e[cnt].w=ww;//需注意a[1]和a[qq]也要建边！
}
sort(e+1,e+cnt+1,cmp);//从小到大排序~~~
for (int i=1;i<=cnt;i++){//相信各位都了解这是干什么的~
int fu=find(e[i].u);
int fv=find(e[i].v);
if (fu!=fv){
fa[fu]=fv; ans+=e[i].w; t++;
if (t==n-1){
break;
}
}
}
if (t<n-1) cout<<-1;//如果小于需要的，代表不行，输出-1.
else cout<<ans;//反之输出答案~
return 0;
}