我在上一次的Facebook Hacker Cup中发现了一个问题(所以这不是我的作业,我只是觉得这很有趣),而且我也想到了一个好奇但相当好的解决方案。你可以帮我检查一下我的想法吗?以下是任务:
所以我这样想:在构建图的同时,让我们有一个单独的数组存储每个城市有多少邻居(即与给定城市相连的道路数)。在示例中,城市0有2个邻居,城市1有3个邻居,以此类推。我们称这些数字为特定城市的“城市值”。给定一个具有N个城市和M条双向道路连接这些城市的网络。前K个城市很重要。您需要删除最少数量的道路,以便在剩余的网络中没有包含重要城市的循环。循环是指至少三个不同城市的序列,其中每对相邻城市都由一条路连接,序列中的第一个城市和最后一个城市也由一条路连接。
输入
第一行包含测试用例数T。每个测试用例开始于包含整数N、M和K的一行。它们分别表示城市数量、道路数量和重要城市数量。城市从0到N-1编号,重要城市从0到K-1编号。接下来的M行包含两个整数a[i]和b[i],0 ≤ i < M,表示一条连接两个不同城市的道路。
保证0 ≤ a[i],b[i] < N且a[i] ≠ b[i]。两个城市之间最多只有一条路。
输出
对于从1到T编号的每个测试用例,输出“Case#i:”后跟一个整数,即需要删除的最少数量的道路,以便没有包含重要城市的循环。限制条件
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ K ≤ N示例
在第一个示例中,我们有N = 5个城市,由M=7条路连接,城市0和1很重要。我们可以删除连接(0,1)和(1,2)的两条路,剩余网络不包含包含重要城市的循环。请注意,在剩余网络中,只包含非重要城市的循环,并且也有多种方法可以去除两条路并满足所有条件。不能仅删除一条路并摧毁所有包含重要城市的循环。示例输入
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4
在获取完整输入后,我们遍历整个城市值数组,寻找值为1的城市。当到达其中一个时,意味着它不能在一个环中,所以我们减小其值,“删除”(不影响一般性)连接它和其唯一邻居的道路,并减小邻居的值。之后,我们递归地前往邻居,检查是否存在相同的东西。如果值为1,则重复方案并递归更深。如果不是,则不要触摸。
经过该操作后,我们清除了所有不是循环的部分,并且不能成为循环的部分。我们也摆脱了所有不合理的道路。因此,我们调用另一个函数,这次仅适用于重要城市。因此,我们使用顶点1——在使用上述段落中描述的函数之后,它的值不能为1(因为该功能已将其设为零),因此它要么为0,要么为> 1的某些值。在第一种情况下,我们不需要做任何事情。在后者中,我们必须使值为1,这是通过执行value-1次拆除来完成的。与前一段类似,在每次删除后,我们降低此城市和其邻居的价值,并删除道路。我们将其重复用于所有k个重要城市,从所有重要城市中总结值-1,并得出答案。
这有意义吗?对我尝试过的所有测试都有效,我想相信它是正确的,但我总觉得可能会有漏洞。您能检查一下吗?如果不好,请解释一下原因,并描述一下这个思考过程中的任何正确之处 : )