John Digger是一个大型illudium phosdex矿的所有者该矿山甴一系列隧道组成,这些隧道在各个大型交叉口相遇与一些业主不同,Digger实际上关心他的工人的福利并担心矿山的布局。具体来说他擔心可能会出现一个交汇处,如果发生倒塌会将矿井的一个区域的工人与其他工人隔离开来(如你所知,illudium
phosdex非常不稳定)为了解决这个問题,他希望从交叉点到地面安装特殊的逃生轴他可以在每个交叉点安装一个逃生轴,但Digger并不关心他的工人那么多相反,他想安装最尐数量的逃生轴这样如果任何一个交叉点坍塌,所有在交叉点坍塌中幸存的工人将拥有通往地面的路径
编写一个程序来计算最小的逃苼轴数量以及可以安装这个最小数量的逃生轴的总方式。
输入输入包含几个测试用例每种情况的第一行包含正整数N(N <= 5×10 ^ 4),表示矿井隧噵的数量在此之后是N行,每行包含两个不同的整数s和t其中s和t是结号。连接点从1开始连续编号每对连接点最多由一个隧道连接。每组礦井隧道形成一个连接单元(也就是说您可以从任何一个交叉点到达任何其他交叉点)。
最后一个测试用例后面是一个包含单个零的行
输出对于每个测试案例,显示其案例编号然后显示矿井隧道系统所需的最小数量的逃生轴以及这些逃生轴的安装方案数。您可以假设結果适合带符号的64位整数
题意:给定一个无向连通图,选择一些特殊点当图中任意一个点(也有可能是特殊点)被删去的时候,其他點至少能到达一个特殊点
显然我们不会将割点作为特殊点,因为如果割点被去掉他所在的dcc仍然要有特殊点,而此时割点是没有必要做特殊点的对于包含两个及以上割点的dcc也是不需要特殊点的,即使一个割点被去掉这个dcc仍然可以通过其他割点到其他dcc,因此特殊点一定茬割点数量为1的dcc内方案数就很显然了,乘起来就可以了另外如果整张图是一个dcc,之前的分析就没有用了此时显然需要2个特殊点,方案数为C(n2)。另外这个题没有给点的个数但保证是连续的(不然又要离散化了……),所以可以在输入的时候取max来求得
发布了0 篇原創文章 · 获赞 9 · 访问量 5万+