求助,WA 掉 9 个点

回复帖子

@yyfcpp 2018-03-14 00:10 回复

评测链接

//【P2330】[SCOI2005] 繁忙的都市 - 洛谷 - 10
#include <iostream>
#include <algorithm>

struct Edge {
    int u;
    int v;
    int c;
    Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
    Edge() {}
};

constexpr int kMaxN = 300;
constexpr int kMaxM = 50000;

Edge e[kMaxM + 5];
int fa[kMaxN + 5];

int find(int x) {
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}

void merge(int u, int v) {
    u = find(u);
    v = find(v);
    fa[v] = u;
}

int main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) // 又一次忘记初始化并查集 
        fa[i] = i;
    for (int i = 1; i <= m; ++i) {
        int u;
        int v;
        int c;
        std::cin >> u >> v >> c;
        e[i] = Edge(u, v, c);
    }
    std::sort(e + 1, e + m + 1, [](const Edge &e1, const Edge &e2) {
        return e1.c < e2.c;
    });

    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
        if (find(e[i].u != find(e[i].v))) {
            merge(e[i].u, e[i].v);
            if (++cnt == n - 1) {
                std::cout << cnt << " " << e[i].c << std::endl;
                return 0;
            }
        }
    }
}
@小闸蟹 2018-03-14 06:45 回复

没有没有,我昨晚是太困了老眼昏花,躺床上看代码想当然就发出来了(逃@yyfcpp

@Arashi丶 2018-03-14 07:31 回复
return fa[x] = find(fa[x]);

这个改成这样试试 我以前这么写好像是炸过

fa[x] = find (fa[x]);
return fa[x];
@Chjka 2018-03-14 09:36 回复

盯了5min,您看看这一句呀。

if (find(e[i].u != find(e[i].v)))

@小闸蟹 2018-03-14 09:53 回复

破案了。。。 (我昨晚一直看着算法,感觉没毛病啊。。。)@Chjka