C++：寻找环边最小和的快速算法

Question

我有一个无向带权图，想要找到所有环的边权最小值之和。 也就是说，如果没有环，则答案为0。 如果只有一个环，答案为该环中边权的最小值。 如果有多个环，则是这些最小权重的总和。

我的算法使用了某种Prims算法。 我只是添加最重的边，当形成一个环时，将权重加到答案值中。

我认为这是正确的，因为我的所有测试用例都显示出正确的答案。

但是必须有一个错误，在这之前我还没有找到。

struct connection {
    int a, b, cost;

    bool operator<(const connection rhs) const {
        return cost < rhs.cost || (cost == rhs.cost && (a < rhs.a || (a == rhs.a && b < rhs.b)));
    }
};

int n, m, researchers; // Amount of vertices, edges
std::list<connection> *adj; // Array of adjancency lists
std::list<int> *used;
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost) {
    connection temp;
    temp.a = v;
    temp.b = w;
    temp.cost = cost;
    adj[v].push_back(temp);
    temp.a = w;
    temp.b = v;
    adj[w].push_back(temp);
}

bool isUsed(int u, int v) {
    for (std::list<int>::iterator it = used[u].begin(); it != used[u].end(); ++it) {
        int te = *it;
        if (te == v) return true;
    }
    return false;
}

void expand(int u) {
    for (std::list<connection>::iterator it = adj[u].begin(); it != adj[u].end(); ++it) {

        connection v = *it;

        if (isUsed(u, v.b)) continue;

        used[v.b].push_back(u);
        used[u].push_back(v.b);

        priorityQ.insert(v);
    }
}

void PrimR(int u, bool added[]) {
    added[u] = true;
    expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

    added[u] = true;

    expand(u);

    while (priorityQ.size() > 0) {
        connection now = *priorityQ.rbegin();
        priorityQ.erase(*priorityQ.rbegin());

        if (added[now.b]) {
            researchers += now.cost;
        }
        else {
            PrimR(now.b, added);

        }
    }

}

int main()
{

    int t;

    // loop over all test cases
    scanf("%d ", &t);
    for (int i = 1; i <= t; i++) {

        // read input nodes n, connections m
        scanf("%d %d", &n, &m);

        adj = new std::list<connection>[n];

        //read connections and save them
        for (int j = 0; j < m; j++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            addEdge(a - 1, b - 1, c);
        }

        researchers = 0;

        // Use of prim with heaviest edges first
        bool *added = new bool[n];
        used = new std::list<int>[n];

        for (int j = 0; j < n; j++) {
            added[j] = false;
        }

        for (int j = 0; j < n; j++) {
            if (!added[j]) {
                Prim(j, added);
            }
        }


        // print desired output
        printf("Case #%d: %d\n", i, researchers);

        delete[] adj;
        delete[] added;
        delete[] used;
    }
    return 0;
}

你知道我做错了什么吗？

- Timotheus

---

基本上，这个问题是要找到循环，所以请参见 http://stackoverflow.com/a/549402/3134621 Tarjan 等。 - deviantfan

Answer 1

我没有考虑到两个节点之间可能有多个连接。

我的下面的代码可以解决这个问题：

struct connection {
    int a, b, cost, id;

    bool operator<(const connection rhs) const {
        return cost < rhs.cost || (cost == rhs.cost && id < rhs.id);
    }
};

int n, m, researchers; // Amount of vertices, edges
std::list<connection> *adj; // Array of adjancency lists
std::set<connection> priorityQ;

void addEdge(int v, int w, int cost, int id) {
    connection temp;
    temp.a = v;
    temp.b = w;
    temp.cost = cost;
    temp.id = id;
    adj[v].push_back(temp);
    temp.a = w;
    temp.b = v;
    adj[w].push_back(temp);
}

void deleteEdge(int v, int w, int id) {
    for (std::list<connection>::iterator it = adj[v].begin(); it != adj[v].end(); ++it) {
        if ((*it).id == id) {
            adj[v].erase(it);
            break;
        }
    }
    for (std::list<connection>::iterator it = adj[w].begin(); it != adj[w].end(); ++it) {
        if ((*it).id == id) {
            adj[w].erase(it);
            break;
        }
    }
}

void expand(int u) {
    for (std::list<connection>::iterator it = adj[u].begin(); it != adj[u].end(); ++it) {

        connection v;
        v.a = (*it).a < (*it).b ? (*it).a : (*it).b;
        v.b = (*it).a < (*it).b ? (*it).b : (*it).a;
        v.cost = (*it).cost;
        v.id = (*it).id;

        priorityQ.insert(v);
    }
}

void PrimR(int u, bool added[]) {
    added[u] = true;
    expand(u);
}

// Prim algorithm
void Prim(int u, bool added[]) {

    added[u] = true;

    expand(u);

    while (priorityQ.size() > 0) {
        connection now = *priorityQ.rbegin();
        priorityQ.erase(*priorityQ.rbegin());

        deleteEdge(now.a, now.b, now.id);

        if (added[now.b] && added[now.a]) {
            researchers += now.cost;
        }
        else if (added[now.b]) {
            PrimR(now.a, added);
        }
        else if (added[now.a]) {
            PrimR(now.b, added);
        }
    }

}

int main()
{

    int t;

    // loop over all test cases
    scanf("%d ", &t);
    for (int i = 1; i <= t; i++) {

        // read input nodes n, connections m
        scanf("%d %d", &n, &m);

        adj = new std::list<connection>[n];

        //read connections and save them
        for (int j = 0; j < m; j++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            addEdge(a - 1, b - 1, c, j);
        }

        researchers = 0;

        // Use of prim with heaviest edges first
        bool *added = new bool[n];

        for (int j = 0; j < n; j++) {
            added[j] = false;
        }

        for (int j = 0; j < n; j++) {
            if (!added[j]) {
                Prim(j, added);
            }
        }


        // print desired output
        printf("Case #%d: %d\n", i, researchers);

        delete[] adj;
        delete[] added;
    }
    return 0;
}

- Timotheus

Answer 2

你可以使用 Floyd-Warshall 算法。

Floyd-Warshall 算法可以找到所有顶点对之间的最短路径。

并且在考虑每个可能的顶点 u 后，(u,u) -> (u,u) 的最短路径就是你要查找的答案。

该算法的运行时间为 O(n^3)。

- CodingLab