5

（这来自最近完成的编程竞赛）

给你 G，一个有 N 个节点和 N-1 条边的连通图。

（请注意，这意味着 G 形成一棵树。）

G 的每条边都是有向的。（不一定向上到任何根）

对于 G 的每个顶点 v，可以反转零个或多个边，使得从每个其他顶点 w 到 v 都有一条有向路径。让实现这一点的边反转的最小可能数量为 f(v)。

我们可以通过什么线性或对数线性算法来确定具有最小总 f(v) 的顶点子集（包括这些顶点的 f(v) 的值）？

例如考虑具有这些边的 4 个顶点图：

A<--B
C<--B
D<--B

f(A) = 2, f(B) = 3, f(C) = 2 和 f(D) = 2...

..因此，所需的输出是 {A,C,D} 和 2

（注意我们只需要计算具有最小 f(v) 的顶点的 f(v) - 不是全部）

代码：

对于后代，这里是解决方案的代码：

int main()
{
    struct Edge
    {
        bool fwd;
        int dest;
    };

    int n;
    cin >> n;

    vector<vector<Edge>> V(n+1);

    rep(i, n-1)
    {
        int src, dest;
        scanf("%d %d", &src, &dest);

        V[src].push_back(Edge{true, dest});
        V[dest].push_back(Edge{false, src});
    }

    vector<int> F(n+1, -1);

    vector<bool> done(n+1, false);

    vector<int> todo;
    todo.push_back(1);
    done[1] = true;
    F[1] = 0;

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (done[e.dest])
                continue;

            if (!e.fwd)
                F[1]++;
            done[e.dest] = true;
            todo.push_back(e.dest);
        }
    }

    todo.push_back(1);

    while (!todo.empty())
    {
        int next = todo.back();
        todo.pop_back();

        for (Edge e : V[next])
        {
            if (F[e.dest] != -1)
                continue;

            if (e.fwd)
                F[e.dest] = F[next] + 1;
            else
                F[e.dest] = F[next] - 1;

            todo.push_back(e.dest);
        }
    }

    int minf = INT_MAX;

    rep(i,1,n)
        chmin(minf, F[i]);

    cout << minf << endl;

    rep(i,1,n)
        if (F[i] == minf)
            cout << i << " ";
    cout << endl;

}
4

1 回答 1

7

我认为以下算法可以正常工作，并且肯定可以在线性时间内工作。

该算法的动机如下。假设您已经知道某个单个节点 v 的 f(v) 的值。现在，考虑与 v 相邻的任何节点 u。如果我们想计算 f(u) 的值，我们可以重用来自f(v) 来计算它。请注意，为了从图中的任何节点 w 到 u，必须发生以下两种情况之一：

  1. 这条路径穿过连接 u 和 v 的边。在这种情况下，我们从 w 到 u 的方式是从 w 到 v，然后沿着从 v 到 u 的边。
  2. 那条路径不通过连接 u 和 v 的边。在这种情况下，我们从 w 到 u 的方式与我们从 w 到 v 的方式完全相同，只是我们一到达 u 就停止.

这个观察很重要的原因是，它意味着如果我们知道从任何节点翻转到 v 的边的数量，我们可以轻松修改它以获得我们要翻转的边集你的任何节点。具体来说，它将是与以前相同的边集，除了我们想要引导连接 u 和 v 的边，以便它将 v 连接到 u，而不是反过来。

如果从 u 到 v 的边最初是定向的 (u, v)，那么我们必须翻转所有翻转的正常边以使每个节点都指向 v，再加上一条边以使 v 重新指向 u。因此 f(u) = f(v) + 1。否则，如果边最初是有向的 (v, u)，那么我们要翻转的边集将与之前相同（将所有东西都指向 v），除了我们不会翻转边缘（v，u）。因此 f(u) = f(v) - 1。

因此，一旦我们知道单个节点 v 的 f 值，我们就可以为每个相邻节点 u 计算它，如下所示：

f(u) = f(v) + 1    if (u, v) is an edge.
f(u) = f(v) - 1    otherwise

这意味着我们可以为所有节点 v 计算 f(v)，如下所示：

  1. 计算任意选择的某个初始节点 v 的 f(v)。
  2. 从 v 开始做 DFS。当到达节点 u 时，使用上述逻辑计算其 f 分数。

剩下要做的就是为某个初始节点计算 f(v)。为此，我们可以从 v 向外运行 DFS。每次我们看到边缘指向错误的方向时，我们都必须翻转它。因此，f(v) 的初始值由我们在初始 DFS 期间发现的错误指向边的数量给出。

因此，我们可以在 O(n) 时间内计算每个节点的 f 分数，方法是执行初始 DFS 计算初始节点的 f(v)，然后使用辅助 DFS 计算每个其他节点 u 的 f(u)。然后，您可以对 n 个 f 分数中的每一个进行 for 循环以找到最低分数，然后再执行一个循环以找到具有该 f 分数的所有值。这些步骤中的每一步都需要 O(n) 时间，因此整个算法也需要 O(n) 时间。

希望这可以帮助！这是一个很棒的问题！

于 2012-08-27T20:43:27.740 回答