POJ1861 - Network

2016/11/14

一道 MST 的裸题。

Prim 实现比 Kruskal 的长了 0.6 倍,性能只有 0.1 倍提升。

所以说:不要乱搞优化, std::priority_queue 大法好,不行还有平板电视 __gnu_pbds::priority_queue

代码 (Prim + zkw线段树优化)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstring>
#include <limits>
#include <vector>
using namespace std;
const int ESIZ = 1E5;

struct tgno {
    int u, v, w; int en; // Enable?
    tgno *n;
} POOL[ESIZ]; int ppos;
tgno* Head[ESIZ];
int vis[ESIZ];
int N, M;

void _add(int u, int v, int w) {
    POOL[ppos].u = u; POOL[ppos].v = v;
    POOL[ppos].w = w; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v, int w) {
    _add(u, v, w); _add(v, u, w);
}

#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
struct zkwtree {
    int mmin[ESIZ<<1], mark[ESIZ<<1], uark[ESIZ<<1];
    int cap, M;
    void mkTree(int c) {
        cap = c; for(M=1;M<c;M<<=1);
        memset(mmin, 0x3F, sizeof(mmin)); memset(mark, 0x00, sizeof(mark));
        memset(uark, 0x00, sizeof(uark));
        for(int i=0;i<cap;i++) mark[M+i] = i+1;
    }
    void fix(int cur) {
        cur >>= 1;
        for(;cur;cur>>=1) {
            mmin[cur] = min(mmin[lson(cur)], mmin[rson(cur)]);
            mark[cur] = (mmin[cur] == mmin[lson(cur)] ? mark[lson(cur)] : mark[rson(cur)]);
            uark[cur] = (mmin[cur] == mmin[lson(cur)] ? uark[lson(cur)] : uark[rson(cur)]);
        }
    }
    int top() { return mmin[1]; }
    int top_pos() { return mark[1]; }
    int top_u() { return uark[1]; }
    void pop() { mmin[M-1+mark[1]] = 0x3F3F3F3F; uark[M-1+mark[1]] = 0; fix(M-1+mark[1]); }
    void change(int k, int u, int v) { mmin[M-1+k] = v; uark[M-1+k] = u; fix(M-1+k); }
    int at(int k) { return mmin[M-1+k]; }
} Q;

vector<pair<int, int> > GG;

int tmax = numeric_limits<int>::min();
void Prim(int S) {
    Q.mkTree(N);
    Q.change(S, 0, 0);
    for(int i=0;i<N;i++) {
        int pp = Q.top(), cur = Q.top_pos(), uu = Q.top_u(); Q.pop(); vis[cur] = 1;
        if(cur != S) { tmax = max(tmax, pp); GG.push_back(make_pair(uu, cur)); }
        typedef tgno* It;
        for(It i=Head[cur];i;i=i->n) {
            if(!vis[i->v] && Q.at(i->v) > i->w) {
                Q.change(i->v, i->u, i->w);
            }
        }
    }
}

int main() {
    cin >> N >> M;
    
    int u, v, w;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    
    Prim(1);

    cout << tmax << endl << N-1 << endl; int _ = N-1;
    for(int i=0;i<_;i++) {
        cout << GG[i].first << " " << GG[i].second << endl;
    }
}

代码 (Kruskal)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;
const int ESIZ = 1E5;

struct tgno {
    int u, v, w; int en; // Enable?
    tgno *n;
} POOL[ESIZ]; int ppos;
tgno* Head[ESIZ];
int vis[ESIZ];
int N, M;

void _add(int u, int v, int w) {
    POOL[ppos].u = u; POOL[ppos].v = v;
    POOL[ppos].w = w; POOL[ppos].n = Head[u];
    Head[u] = &POOL[ppos++];
}

void addEdge(int u, int v, int w) {
    _add(u, v, w); _add(v, u, w);
}

struct djset {
    int Fa[ESIZ];
    void mkSet(int cap) { for(int i=0;i<=cap;i++) Fa[i] = i; }
    int find(int x) { return x==Fa[x]?x:Fa[x]=find(Fa[x]); }
} S;

bool cmp(const tgno& a, const tgno& b) {
    return a.w < b.w;
}

vector<pair<int, int> > GG;
int tmax = numeric_limits<int>::min();
void Kruskal() {
    S.mkSet(N);
    sort(POOL, POOL+ppos, cmp);
    size_t s = N-1; int i = 0;
    while(GG.size() < s) {
        if(S.find(POOL[i].u) != S.find(POOL[i].v)) {
            GG.push_back(make_pair(POOL[i].u, POOL[i].v));
            tmax = max(tmax, POOL[i].w);
            S.Fa[S.find(POOL[i].u)] = S.find(POOL[i].v);
        }
        ++i;
    }
}

int main() {
    cin >> N >> M;
    
    int u, v, w;
    for(int i=0;i<M;i++) {
        cin >> u >> v >> w;
        addEdge(u, v, w);
    }
    
    Kruskal();

    cout << tmax << endl << N-1 << endl; int _ = N-1;
    for(int i=0;i<_;i++) {
        cout << GG[i].first << " " << GG[i].second << endl;
    }
}