2020-12-03 02:27:46 登录注册 RSS

当前位置: 公理网 >> 正义之家 >> 并查集1069关押罪犯

并查集1069关押罪犯
发布时间:10-19| 来源:公理网 | 点击发表评论
1069关押罪犯题目描述DescriptionS城现有两座监狱一共关押着N名罪犯编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久如果客观条件具备则随时可能爆发冲突。我们用“怨气值”一个正整数值来表示某两名罪犯之间的仇恨程度怨气值越大则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱他们俩之间会发生摩擦并造成影响力为c的冲突事件。每年年末警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表然后上报到S城Z市长那里。公务繁忙的Z市长只会去看列表中的第一个事件的影响力如果影响很坏他就会考虑撤换警察局长。在详细考察了N名罪犯间的矛盾关系后警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配以求产生的冲突事件影响力都较小从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨那么他们一定会在每年的某个时候发生摩擦。那么应如何分配罪犯才能使Z市长看到的那个冲突事件的影响力最小这个最小值是少输入描述InputDescription第一行为两个正整数N和M分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的M行每行为三个正整数ajbjcj表示aj号和bj号罪犯之间存在仇恨其怨气值为cj。数据保证且每对罪犯组合只出现一次。输出描述OutputDescription共1行为Z市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件请输出0。样例输入SampleInput4614253423351212283511366182418053412884样例输出SampleOutput3512数据范围及提示DataSizeHint罪犯之间的怨气值如下面左图所示右图所示为罪犯的分配方法市长看到的冲突事件影响力是3512由2号和3号罪犯引发。其他任何分法都不会比这个分法更优。【数据范围】对于30%的数据有N≤15。对于70%的数据有N≤2000M≤50000。对于100%的数据有N≤20000M≤100000。分析最理想的情况是将有怒气冲突的罪犯分开关押但只有两个监狱可能无法避免冲突于是将怒气按从大到小排列先将当前怒气最大、冲突最严重的犯人分开关押直到发现有个犯人无法调和即与另个监狱里的罪犯已有冲突、怒气而且按序是比此次怒气大的所以输出这次无法调和的怒气注意完全调和、解决冲突怒气输出0.所以此处查找有冲突的犯人是否已在同一监狱用到查找将可以避免冲突的犯人分到不同监狱关押用到合并两个合并将犯人和监狱合并所以此题用的就是并查集对数据从大到小排序优先解决怒气高的一组犯人应该算贪心的思想。#includecstdio#includealgorithmusingnamespacestd;constintmaxn2000010;intp[2*maxn];//加倍用到对立面x在p[x]监狱里不在p[xn]里intFind(intx){returnxp[x]?x:p[x]Find(p[x]);//查找}structCriminal{intx,y;intanger;booloperator(constCriminala)const{if(angera.anger)returntrue;//重载操作符按怒气从大到小排列returnfalse;}}crim[100001];intmain(){intn,m,ans;scanf(%d%d,n,for(inti0;i2*n;i){p[i]}for(intiii)scanf(%d%d%d,crim[i].x,crim[i].y,crim[i].anger);sort(crim,crimm);crim[m].angerans//若无冲突输出怒气为0for(intiii){intfxFind(crim[i].x);//查找此人关在哪个监狱intfyFind(crim[i].y);if(fxfy){//若xy已经在同一个监狱里了由于怒气是从大到小排序的所以此时怒气即所求怒气值ansbreak;}p[fx]Find(crim[i].yn);//因为这对犯人怒气值目前最大所以分配在互异的监狱里p[fy]Find(crim[i].xn);}printf(%d\n,crim[ans].anger);return0;}点赞评论1Hadoop与Spark并行度设置问题(mr、spark任务提交参数的设置、spark-submit参数调优)zx_loveDream__Boy:读取文件的并行度是取决于文件存储的block数量;spark任务执行的并行度是根据spark参数、spark执行算子中指定的并行度来控制的(如果不指定,那默认实际执行的并行度和文件读取的并行度是一致的)。意义是在于,很多人在spark任务实际执行的算子中不去指定这个并行度,导致实际执行的并行度是由文件存储时block数决定,导致并行度的不合理;如果一个会被经常使用的文件他的block数不合理,建议是重新读写一遍,重新改变他的并行度,可以避免每次使用时需要重分区的shuffle操作

最新新闻

手机浏览

公理网 版权所有

公理网 Total 0.030699(s) query 6, 报料QQ:点击这里

给我发消息