本文主要是介绍uva 10985 - Rings'n'Ropes( 最短路Folyd),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目连接:uva 10985 - Rings'n'Ropes
题目大意:给出n和m,表示有n个戒指和m条绳子,每条绳子的长度为1,给出每根绳子连接的戒指,然在左右手各握住一个戒指,拉直,问说最多有多少个绳子被绷直。
解题思路:首先先用Floyd算法将每两个戒指之间的最短距离求出(因为向两端扯的时候,最大距离便是连接两个戒指的最短距离),然后枚举两枚戒指,找出中间所有的点(f[x][i] + f[i][y] == f[x][y]);然后在将两点之间所有的点枚举两点,只有这两点之间存在边,并且f[x][i] != f[x][j];
这篇关于uva 10985 - Rings'n'Ropes( 最短路Folyd)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!