我们给了N对.每对包含两个数字.我们必须找到最大数K,这样如果我们从给定的N对中采用J(1 <= J <= K)对的任意组合,我们在所有那些选择的J对中至少有J个不同的数.我们可以有多个相同的一对.
例如,考虑对(1,2)(1,2)(1,2)(7,8)(9,10)对于这种情况K = 2,因为对于K> 2,如果我们选择三对(1,2),我们只有两个不同的数字,即1和2.
从一个开始检查每个可能的组合将花费大量时间.什么是解决问题的有效算法？
创建一个图，其中每个数字有一个顶点，每对有一条边。
\n如果这个图是链或树，我们有“数字”的数量，等于“对”的数量加一，从这个图中删除任意数量的边后，我们得到的顶点永远不会少于边。
\n现在向该链/树添加一个循环。顶点和边的数量相等。从该图中删除任意数量的边后，我们得到的顶点永远不会少于边。
\n现在添加任意数量的断开连接的组件，每个组件不应包含超过一个周期。再说一遍，删除任意数量的边后，我们得到的顶点永远不会少于边。
\n现在向任何断开连接的组件添加第二个周期。移除所有其他组件后。最后我们的边比顶点多（对比数字多）。
\n所有这些都得出这样的结论：K+1 正是最小可能子图中的边数，该子图由两个循环组成，并且可能有一条连接这些循环的链。
\n对于每个连接的组件，使用 Floyd-Warshall 算法找到经过每个节点的最短周期。
\n然后对于每个不重叠的循环对（在单个组件中），使用 Dijkstra\xe2\x80\x99s 算法，从一个循环中至少有 3 个边的任何节点开始，找到到另一个循环的最短路径；并计算两个循环的长度和连接它们的最短路径。对于每对重叠的循环，只需计算它们的边数即可。
\n现在找到所有这些子图的最小长度。并减去1。
\n如果图中至少有一个双环分量，则上述算法计算 K。如果没有这样的组件，则 K = N。
\n| 归档时间： |
|
| 查看次数： |
1019 次 |
| 最近记录： |