Java教程

2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1009 KD-Graph(克鲁斯卡尔算法)

本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1009 KD-Graph(克鲁斯卡尔算法),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1009&cid=984

 

题意:

称一个带权无向联通图为KD图,当它满足以下条件

1、n个点被分为k个组,每个组至少有一个点

2、若p和q在同一个组,p和q之间存在至少一条路径满足路径上最大边权<=D

3、若p和q不在同一个组,p和q之间没有路径满足路径上最大边权<=D

给出图和k,求最小的D

 

条件2:p和q之间存在一条路径满足全部边权<=D

条件3:p和q之间所有路径的所有边权>D

 

这就是克鲁斯卡尔算法运行到当前有k个组的时候的状态

 

这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1009 KD-Graph(克鲁斯卡尔算法)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!