网站建设 政府采购网络营销的主要方式和技巧
[题目通道]([ABC352E] Clique Connect - 洛谷)
鄙人今日写人生第一篇题解
希望管理大大通过
首先，我们先看题:
它说一共有n个点，m回操作。。。
每次操作 都有 一个Ki 和 Ci
Ki代表有Ki个点,Ci代表每条边所赋的边权一看就知道这是个最小生成树的板子
我使用了著名的 kruskal
话不多说贴上代码
#include<bits/stdc++.h>
#define int long longusing 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;
}