CCF-CSP题解 201412-4 最优灌溉

\(kruskal\)，有兴趣\(heap\_prim\)。\(stl\ pq\)实现复杂度相同。

#include <bits/stdc++.h>

using namespace std;

struct tEdge {

    int a, b, c;

    bool operator < (const tEdge &y) const {

        return c < y.c;

    }

};

tEdge edge[100005];

int fa[1005];

int father(int x) {return (fa[x] == x) ? x : (fa[x] = father(fa[x]));}

bool combine(int x, int y) {

    int fx = father(x), fy = father(y);

    if (fx != fy) {fa[fx] = fy; return true;}

    return false;

}

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++i) scanf("%d%d%d", &edge[i].a, &edge[i].b, &edge[i].c);

    sort(edge, edge + m);

    for (int i = 1; i <= n; ++i) fa[i] = i;

    int ans = 0;

    for (int i = 0, k = 0; k < n - 1; ++i)

        if (combine(edge[i].a, edge[i].b) == true) {++k; ans += edge[i].c;}

    printf("%d", ans);

    return 0;

}

#include <bits/stdc++.h>

using namespace std;

int to[200005], nex[200005], w[200005], head[1005], cnt;

void addEdge(int a, int b, int c) {

    to[cnt] = b; nex[cnt] = head[a]; w[cnt] = c; head[a] = cnt++;

    to[cnt] = a; nex[cnt] = head[b]; w[cnt] = c; head[b] = cnt++;

}

struct tNode {

    int id, dis;

    tNode(int i, int d) : id(i), dis(d) {}

    bool operator < (const tNode &y) const {

        return dis > y.dis;

    }

};

int done[1005], dis[1005];

int heap_prim() {

    memset(done, 0, sizeof(done));

    memset(dis, 0x3f, sizeof(dis));

    int ans = 0;

    priority_queue<tNode> que;

    dis[1] = 0;

    que.push(tNode(1, 0));

    while (!que.empty()) {

        tNode x = que.top(); que.pop();

        if (done[x.id]) continue;

        ans += x.dis;

        done[x.id] = 1;

        dis[x.id] = 0;

        for (int i = head[x.id]; i != -1; i = nex[i]) {

            int l = to[i];

            if (dis[l] > w[i]) {

                dis[l] = w[i];

                que.push(tNode(l, dis[l]));

            }

        }

    }

    return ans;

}

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    memset(head, -1, sizeof(head));

    cnt = 0;

    for (int _ = 0, a, b, c; _ < m; ++_) {

        scanf("%d%d%d", &a, &b, &c);

        addEdge(a, b, c);

    }

    printf("%d", heap_prim());

    return 0;

}

巴特西

CCF-CSP题解 201412-4 最优灌溉

最新文章

热门文章