请选择 进入手机版 | 继续访问电脑版

PIPI OJ 1118: 继续畅通工程(并查集+最小生成树)

[复制链接]
冰宇 发表于 2020-12-31 19:00:12 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
菜鸟生成记(18)

1118: 继续流通工程

又双叒叕是最短路径的水题;差别的是,在构造最小生成树前,题目中已经规定一些已经建好了(这些边已经在生成树内里了);从未建好的边中选择最优边加入生成树;直到所有的极点都被并入一个连通分量(生成树)中;

AC代码

[code]#includeusing namespace std;typedef struct st ak;const int N=1e+4+10;//因为1>z>>f;                        if(f==1)//1体现该边已经建成了                         {//直接并查集走起                                 t1=find(x);//找x的祖先                                 t2=find(y);//找y的祖先                                 pre[y]=t1;//y认x的祖先为自己的祖先                                 pre[t2]=t1;//y的祖先认x的祖先为自己的祖先                                //x和x的祖先与y和y的祖先并入一个连通分量(生成树)                         }                        else//0体现该边还未建成,待选择                         {//                                 s[num].v1=x,s[num].v2=y,s[num].w=z;                                num++;                        }                        }                sort(s,s+num,cmp);//按权值从小到大排序                 for(int i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )