图论|2021-08-10 SSL 模拟赛 T2 并查集|最小生成树|#

2021-08-10 SSL 模拟赛 T2 【图论|2021-08-10 SSL 模拟赛 T2】依旧是没有标题的一题

文章图片

文章图片

题面就不复制了，太长了。
思路：显然，我们争取用最少的费用获取所有情报，那么每一条线路都必须是有用的，就是删掉这条线后将会出现一部分情报无法获得的情况。
那这不就是个最小生成树的模板题吗？
我们把派出一个人所需要的费用看做是向不存在图中的 0 号节点连一条边，那么这题就转化成了一道最小生成树的模板题。
我们用克鲁斯卡尔算法去解决。
最小生成树的实现就不写了，也比较简单，时间复杂度O ( m ? l o gm ) O(m*log~m) O(m?log m)
代码：

#include #include #include #include #include #include #define r register #define rep(i,x,y) for(r ll i=x; i<=y; ++i) #define per(i,x,y) for(r ll i=x; i>=y; --i) using namespace std; typedef long long ll; ll n,g[1010][1010],v[1010],top,f[1010]; ll MST,tot; struct node { ll x,y,k; }a[1010*1010]; bool cmp(node x,node y) { return x.k'9') if(ch=='-') f=-1; res=res*10+ch-'0'; while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0'; return res*f; } int main() { scanf("%lld",&n); rep(i,1,n) rep(j,1,n) {g[i][j]=in(); a[++top].x=i; a[top].y=j; a[top].k=g[i][j]; } rep(i,1,n) {scanf("%lld",&v[i]); a[++top].x=0; a[top].y=i; a[top].k=v[i]; a[++top].x=i; a[top].y=0; a[top].k=v[i]; } rep(i,0,n) f[i]=i; sort(a+1,a+top+1,cmp); //最下生成树的排序 rep(i,1,top) {ll x=a[i].x,y=a[i].y,val=a[i].k; if(find(x)!=find(y)) {make(x,y); ++tot; MST+=val; if(tot>=n) break ; } } printf("%lld",MST); return 0; }

图论|2021-08-10 SSL 模拟赛 T2

推荐阅读

女性提前进入更年期的危害女白领应警惕更年期提前来扰

干煸杏鲍菇

如何使用手机上的云服务器？手机的云服务器怎么用

粉饼和散粉的区别和作用

商标自助查询系统官网注册商标如何收费，商标注册证查询网中国商标网

大闸蟹怎么保存才不死

怪物猎人世界特殊装备解锁条件大全怪物猎人世界特殊装备解锁条件大全

mysql允许局域网连接 mysql允许外网登陆

阳光玫瑰亩产量一般多少斤，适合哪些地区种植

一文搞懂什么叫做唯心主义？唯心主义通俗解释

桂林手撕白切鸡做法一招解决你不会切白切鸡的烦恼

全面战争三国诸葛亮怎么招募

手动挡倒车入库视频教程如何倒车入位视频教程，倒车入库视频技巧

标准的java三层代码，java三层架构代码规范

简单的安卓阅读软件,阅读浏览器可离线使用阅读小说更清楚

黑米搭配什么煮粥最好

农村拆迁土地纠纷怎么办手续农村拆迁土地纠纷怎么办？

关于色彩诊断的觉察

农村户口的残疾赔偿金标准是什么？

抑郁症|2021年将有9200万独居者：警惕孤独成为抑郁的温床