51nod 1640 天气晴朗的魔法 二分 + 克鲁斯卡算法(kruskal算法) 做复杂了

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1640

一开始想的时候，看到要使得最大值最小，那这样肯定是二分这个最大值了，然后每一次都跑一次kruskal

这样的复杂度是O(E * 64)，然后被卡TLE了

然后观察到kruskal的时候，如果最大边是val，那么比val大的是不要的了，然后整个数组也是有序的。

比如7、6、5、4、3、2、1等，这个也是可以lower_bound的，然后lower_bound后就能过，600ms

改了lower_bound后，我忘记删除那个if了，居然还是超时。TAT，这数据有点强。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

int n, m;

const int maxn = 2e5 + ;

struct Edge {

    int u, v, w;

    bool operator < (const struct Edge & rhs) const {

        return w > rhs.w;

    }

}e[maxn];

int fa[maxn];

void init() {

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

}

int tofind(int u) {

    if (fa[u] == u) return u;

    else return fa[u] = tofind(fa[u]);

}

void tomerge(int x, int y) {

    x = tofind(x);

    y = tofind(y);

    fa[y] = x;

}

LL nowAns;

bool check(LL val) {

    init();

    int sel = ;

    nowAns = ;

    struct Edge t;

    t.w = val;

    int pos = lower_bound(e + , e +  + m, t) - e;

    for (int i = pos; i <= m; ++i) {

//        if (e[i].w > val) continue;  卡TLE

        if (tofind(e[i].u) == tofind(e[i].v)) continue;

        tomerge(e[i].u, e[i].v);

        nowAns += e[i].w;

        sel++;

        if (sel == n - ) {

            return true;

        }

    }

    return false;

}

void work() {

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

    LL lo = 1e18L, hi = -1e18L;

    for (int i = ; i <= m; ++i) {

        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

        lo = min(lo, (LL)e[i].w);

        hi = max(hi, (LL)e[i].w);

    }

    sort(e + , e +  + m);

    while (lo <= hi) {

        LL mid = (lo + hi) >> ;

        if (check(mid)) {

            hi = mid - ;

        } else lo = mid + ;

    }

    check(lo);

//    printf("%lld\n", nowAns);

    cout << nowAns << endl;

//    struct Edge t;

//    t.w = 3;

//    int pos = lower_bound(e + 1, e + 1 + m, t) - e;

//    cout << pos << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

然后就上网看题解了，然后发现自己做法很复杂了。

感觉是题意弄得我们想复杂了，又魔法连的值，又总和，

正解是kruskal两次，第一次就能找出最大值最小，然后从大的再kruskal一次。

但是为什么还是700ms，有点坑。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

int n, m;

const int maxn = 2e5 + ;

struct Node {

    int u, v, w;

    bool operator < (const struct Node & rhs) const {

        return w < rhs.w;

    }

}e[maxn];

bool cmp(struct Node a, struct Node b) {

    return a.w > b.w;

}

int fa[maxn];

int tofind(int u) {

    if (fa[u] == u) return u;

    else return fa[u] = tofind(fa[u]);

}

void tomerge(int x, int y) {

    x = tofind(x);

    y = tofind(y);

    fa[y] = x;

}

void init() {

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

}

int result() {

    init();

    int sel = ;

    for (int i = ; i <= m; ++i) {

        if (tofind(e[i].u) == tofind(e[i].v)) continue;

        tomerge(e[i].u, e[i].v);

        sel++;

        if (sel == n - ) return e[i].w;

    }

}

void work() {

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

    for (int i = ; i <= m; ++i) {

        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

    }

    sort(e + , e +  + m);

    int mx = result();

    sort(e + , e +  + m, cmp);

    init();

    LL ans = ;

    int sel = ;

    for (int i = ; i <= m; ++i) {

        if (e[i].w > mx) continue;

        if (tofind(e[i].u) == tofind(e[i].v)) continue;

        tomerge(e[i].u, e[i].v);

        sel++;

        ans += e[i].w;

        if (sel == n - ) break;

    }

    printf("%lld\n", ans);

//    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}