logo标签列表

图算法解决方案正确吗？

algorithmgraph
8

我在上一次的Facebook Hacker Cup中发现了一个问题（所以这不是我的作业，我只是觉得这很有趣），而且我也想到了一个好奇但相当好的解决方案。你可以帮我检查一下我的想法吗？以下是任务：

给定一个具有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

所以我这样想：在构建图的同时，让我们有一个单独的数组存储每个城市有多少邻居（即与给定城市相连的道路数）。在示例中，城市0有2个邻居，城市1有3个邻居，以此类推。我们称这些数字为特定城市的“城市值”。
在获取完整输入后，我们遍历整个城市值数组，寻找值为1的城市。当到达其中一个时，意味着它不能在一个环中，所以我们减小其值，“删除”（不影响一般性）连接它和其唯一邻居的道路，并减小邻居的值。之后，我们递归地前往邻居，检查是否存在相同的东西。如果值为1，则重复方案并递归更深。如果不是，则不要触摸。
经过该操作后，我们清除了所有不是循环的部分，并且不能成为循环的部分。我们也摆脱了所有不合理的道路。因此，我们调用另一个函数，这次仅适用于重要城市。因此，我们使用顶点1——在使用上述段落中描述的函数之后，它的值不能为1（因为该功能已将其设为零），因此它要么为0，要么为> 1的某些值。在第一种情况下，我们不需要做任何事情。在后者中，我们必须使值为1，这是通过执行value-1次拆除来完成的。与前一段类似，在每次删除后，我们降低此城市和其邻居的价值，并删除道路。我们将其重复用于所有k个重要城市，从所有重要城市中总结值-1，并得出答案。
这有意义吗？对我尝试过的所有测试都有效，我想相信它是正确的，但我总觉得可能会有漏洞。您能检查一下吗？如果不好，请解释一下原因，并描述一下这个思考过程中的任何正确之处 : )
1
你是否考虑过像下面所示的网络？重要城市的位置并不重要。你的算法在第一阶段会做什么？现在假设所有城市都很重要，在第二阶段会发生什么？ - n. m.
遗憾的是我没有考虑到它。我考虑了桥形图，但只想到像下面这样的图，但中间没有顶点（从一个循环到另一个循环的道路）。对于像下面那样的图，在第一阶段什么也不会做，然后删除一条道路（达到价值1），这将是错误的。所有城市都重要的情况在稍加调整后可以正常工作：在第二个函数中，当特定城市的值在删除一条道路后达到1时，我们还应该深入研究。你提到的这样的图是唯一不能在这里起作用的图吗？ - Straightfw
1
我不认为通过调整、测试和再次调整的方式能够解决这个问题。这里的想法是提出一种严格的证明，而不是只在有限的情况下进行测试。 - n. m.
3个回答
4

这里有一个错误的解决方案。

反例 用于说明你的解决方案。假设正方形中只有一个是重要的。你的解决方案将删除一条路线。

反例

踩票理由：它不是算法，也没有讨论话题发起人提出的算法，示例在重要城市数量K=1和网络结构方面都很琐碎。 - Max Li
4
这不是一个算法，也不是打算成为一个算法。它是一个反例，用来驳斥所提出的算法。该网络的正确答案是0，但算法会输出1。 - n. m.
@n.m. 我没有意识到这是一个反例。从技术上讲，只有在答案被编辑后我才能撤回我的踩（现在已经锁定了）。kilotras，请编辑一些内容（例如添加“反例：”），然后我会重新踩下去。 - Max Li
是的，正如我上面所说的，这种反例破坏了我的算法。不过，它是唯一不能工作的图形类型吗？ - Straightfw
2
对于好奇的人：我选择它作为最佳答案，因为尽管其他答案展示了如何解决问题，但只有这个答案是针对我的问题和我的算法，我所要求的反馈。 - Straightfw
3
如果你能证明最优切割数等于包含重要节点的不同循环的数量，则解决这个问题并不难。
你可以进行深度优先搜索（DFS），跟踪访问过的节点，每当到达一个已经访问过的节点时，就会形成一个循环。为了判断该循环是否包含重要节点，请记录每个节点被访问的深度，并记住当前搜索分支中最后一个重要节点的深度。如果循环的起始深度小于（即较早）最后一个重要节点的深度，则该循环包含重要节点。
C++实现：
// does not handle multiple test cases

#include <iostream>
#include <vector>

using namespace std;

const int MAX = 10000;

int n, m, k;
vector<int> edges[MAX];
bool seen[MAX];
int seenDepth[MAX]; // the depth at which the DFS visited the node

bool isImportant(int node) { return node < k; }

int findCycles(int node, int depth, int depthOfLastImp)
{
    if (seen[node])
    {
        if (seenDepth[node] <= depthOfLastImp && (depth - seenDepth[node]) > 2)
        {
            // found a cycle with at least one important node
            return 1;
        }
        else
        {
            // found a cycle, but it's not valid, so cut this branch
            return 0;
        }
    }
    else
    {
        // mark this node as visited
        seen[node] = true;
        seenDepth[node] = depth;

        // recursively find cycles
        if (isImportant(node)) depthOfLastImp = depth;
        int cycles = 0;
        for (int i = 0; i < edges[node].size(); i++)
        {
            cycles += findCycles(edges[node][i], depth + 1, depthOfLastImp);
        }
        return cycles;
    }
}

int main()
{
    // read data
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++)
    {
        int start, stop;
        cin >> start >> stop;
        edges[start].push_back(stop);
        edges[stop].push_back(start);
    }

    int numCycles = 0;
    for (int i = 0; i < m; i++)
    {
        if (!seen[i])
        {
            // start at depth 0, and last important was never (-1)
            numCycles += findCycles(i, 0, -1);
        }
    }

    cout << numCycles << "\n";
    return 0;
}


* 这里所谓的“不同”是指如果一个环的所有边已经属于不同的环，那么这个环不会被计算。在下面的例子中，我认为循环的数量是2，而不是3：

    A–B
    | |
    C–D
    | |
    E–F
1

我的算法基于以下观察：由于我们不关心仅包含无关紧要节点的循环，因此可以折叠无关紧要节点。我们通过用原始节点的边缘总和替换它们来折叠两个相邻的无关紧要节点，以形成单个无关紧要节点。

当折叠两个无关紧要节点时，我们需要处理两种特殊情况：

  1. 两个节点都连接到同一个不重要的节点U。这意味着原始图中存在一组不重要节点的循环；我们可以忽略该循环，新节点将与单个边连接到同一个不重要节点U。
  2. 两个节点都连接到同一个重要节点I。这意味着原始图中存在一组不重要节点和单个重要节点I的循环；在折叠节点之前，我们需要删除连接它们到重要节点I的一条边，从而消除循环；新节点将与单个边连接到重要节点I。

根据上述节点折叠的定义，算法如下：

  1. 将相邻的不重要节点折叠在一起，直到没有相邻的不重要节点。所有在第二种情况中定义的重要和不重要节点之间被移除的边都计入解决方案。
  2. 找到剩余图形的生成树，并删除未包含在生成树中的所有边。在此步骤中删除的所有边都计入解决方案。

该算法运行时间为O(M)。我相信我可以证明它的正确性，但在花费太多时间之前，我想听听您的反馈意见:-)

非常感谢。不用证明了，我已经看到使用折叠思想和证明的算法了 :) 尽管如此，我仍然非常感激您的见解！ - Straightfw
哦，我现在才意识到我完全误读了你的问题 :-) 说实话，这个问题非常有趣，以至于我几乎没有继续阅读问题的其余部分。 - Krzysztof Kozielczyk
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接