寻找有向图中节点权值GCD最小的路径

Question

我想解决这个问题：有向图上的GCD

我对 SCC、拓扑排序、Kosajaru 算法等还不熟悉

一般来说，我认为我们在路径中使用的节点越多，结果就越好，因为成本（GCD）永远不会增长。这是我解决这个问题的方法：

1. 找到所有强连接的组件（所以我使用尽可能多的节点）和GCD（遍历整个组件的成本）
2. 我们可以将找到的SCC映射到节点并制作DAG，其中单个节点代表整个SCC

通过这种方式，我们将问题简化为在加权 DGA 中寻找最短路径（从任意节点到任意节点）。但我不知道如何以可接受的时间复杂度来处理它。这就是我当前的代码的样子：

#include <iostream>
#include <vector>
#include <list>
#include <stack>

using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;

    return gcd(b, a % b);
}

void top_sort(const vector<list<int>>& g, vector<bool>& visited, vector<int>& order, int node) {
    visited[node] = true;

    for (const int ngbr : g[node]) {
        if (visited[ngbr])
            continue;

        top_sort(g, visited, order, ngbr);
    }

    order.push_back(node);
}

void dfs_0(const vector<list<int>>& rg, const vector<int>& c, vector<bool>& visited, vector<int>& components_gcd, vector<int>& components, int node, int component) {
    visited[node] = true;
    components_gcd[component] = gcd(components_gcd[component], c[node]);
    components[node] = component;

    for (const int ngbr : rg[node]) {
        if (visited[ngbr])
            continue;

        dfs_0(rg, c, visited, components_gcd, components, ngbr, component);
    }
}

void top_sort_components(const vector<list<int>>& scc_g, vector<bool>& visited, stack<int>& order, int node) {
    visited[node] = true;

    for (const int ngbr : scc_g[node]) {
        if (visited[ngbr])
            continue;

        top_sort_components(scc_g, visited, order, node);
    }

    order.push(node);
}

int solve(int n, vector<int> c, vector<vector<int>> edges) {
    vector<list<int>> g(n + 1, list<int>());
    vector<list<int>> rg(n + 1, list<int>());
    for (int i = 0; i < edges.size(); ++i) {
        g[edges[i][0]].push_back(edges[i][1]);
        rg[edges[i][1]].push_back(edges[i][0]);
    }

    vector<bool> visited(n + 1);
    vector<int> order;
    order.reserve(n);

    for (int i = 1; i <= n; ++i) {
        if (!visited[i])
            top_sort(g, visited, order, i);
    }

    reverse(order.begin(), order.end());
    fill(visited.begin(), visited.end(), false);

    vector<int> components_gcd(n + 1);
    vector<int> components(n + 1);
    int component = 0;
    for (const int node : order) {
        if (!visited[node]) {
            ++component;
            dfs_0(rg, c, visited, components_gcd, components, node, component);
        }
    }

    vector<list<int>> scc_g(component, list<int>());
    for (int i = 0; i < edges.size(); ++i) {
        if (components[edges[i][0]] != components[edges[i][1]]) {
            scc_g[components[edges[i][0]]].push_back(components[edges[i][1]]);
        }
    }

    // I struggle here. scc_g is our DAG with SCCs as single nodes
}

如有不清楚的地方请评论。谢谢

Answer 1

步行可以由单个顶点组成。

找到成本最低的顶点。最佳行走（具有最低 GCD）是使用该顶点的行走。 （正如您在问题中提到的，添加顶点没有任何效果。）