note: This article comes from the Internet. Please contact me via lethic@163.com if there is any infringement.
lethic@163.com.

GTGTGG
URAL1416M124750

T(-E1, +E2)TE1E2E2TGG(E2 – E1)GGE2V1V2E1V1V2

TG
1Prim
FF[x][y]TxyFPrim(i, j)ji=c[j]kijF[k][j]=max{F[k][i], (i, j)}FF[j][k]=F[k][j]G(i, j)(i, j)TTFij(i, j)ijT{(i, j) – F[i][j]}(i, j)
1GT2GGT3G(-E1, +E2)E1E2(i, j)(i, j)ij

?Download sourceCode.cpp
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

#include <iostream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 7000, INF = ~0U >> 2;
int n, s[MAXN][MAXN], s2[MAXN][MAXN], f[MAXN][MAXN], c[MAXN], v[MAXN], res1 = 0, res2 = 0;
bool vst[MAXN];
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d", &n);
    re(i, n) re(j, n) s[i][j] = s2[i][j] = INF;
    int m, a, b, len;
    scanf("%d", &m);
    if (!m) {
        if (n > 1) res1 = -INF; res2 = -INF;
        return;
    }
    re(i, m) {
        scanf("%d%d%d", &a, &b, &len); a--; b--;
        if (len < s[a][b]) {s2[a][b] = s2[b][a] = s[a][b]; s[a][b] = s[b][a] = len;} else if (len < s2[a][b]) s2[a][b] = s2[b][a] = len;
    }
    fclose(stdin);
}
void solve()
{
    re(i, n) {f[i][i] = c[i] = vst[i] = 0; v[i] = s[0][i];} vst[0] = 1;
    int l0, l1 = INF, x, y, z;
    re2(i, 1, n) {
        l0 = INF; re(j, n) if (!vst[j] && v[j] < l0) {l0 = v[j]; x = j; y = c[j];}
        if (l0 == INF) {res1 = res2 = -INF; return;}
        vst[x] = 1; res1 += l0; s[x][y] = s[y][x] = INF; if (s2[x][y] < INF && s2[x][y] - l0 < l1) l1 = s2[x][y] - l0;
        re(j, n) if (!vst[j] && s[x][j] < v[j]) {v[j] = s[x][j]; c[j] = x;}
        re(j, n) if (vst[j] && j != x) f[j][x] = f[x][j] = max(f[j][y], l0);
    }
    re(i, n-1) re2(j, i+1, n) if (s[i][j] < INF) {
        z = s[i][j] - f[i][j];
        if (z < l1) l1 = z;
    }
    if (l1 == INF) res2 = -INF; else res2 = res1 + l1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res2) solve();
    pri();
    return 0;
}

PrimO(N2)

2Kruskal
Kruskal(a, b)aS1bS2O(NM)iij(i, j)S1S2T”(a, b)”(a, b)Tij[(i, j) – (a, b)](a, b)DL(a, b)+
1GT(N-1)2G(i, j)3GKruskalKruskal
Kruskal(i, j)S1S2(i, j)E2

?Download sourceCode.cpp
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

#include <iostream>
#include <stdlib.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 7000, MAXM = 130000, INF = ~0U >> 2;
struct edge {
    int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge2 {
    int a, b, len, No;
} ed2[MAXM];
int n, m = 0, m2, u[MAXN], ch[MAXN], nx[MAXN], q[MAXN], res1 = 0, res2 = INF;
void init_d()
{
    re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
    if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int l)
{
    ed[m].a = a; ed[m].b = b; ed[m].len = l; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a = b; ed[m].b = a; ed[m].len = l; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d%d", &n, &m2);
    if (!m2) {
        if (n > 1) res1 = -INF;
        res2 = -INF; return;
    }
    init_d();
    int a, b, len;
    re(i, m2) {
        scanf("%d%d%d", &a, &b, &len);
        ed2[i].No = m; add_edge(--a, --b, len);
        ed2[i].a = a; ed2[i].b = b; ed2[i].len = len;
    }
    fclose(stdin);
}
int cmp(const void *s1, const void *s2)
{
    return ((edge2 *)s1)->len - ((edge2 *)s2)->len;
}
void prepare()
{
    re(i, n) u[i] = ch[i] = nx[i] = -1;
    qsort(ed2, m2, 16, cmp);
}
int find(int x)
{
    int r = x, r0 = x, tmp;
    while (u[r] >= 0) r = u[r];
    while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    return r;
}
void uni(int r1, int r2, int No, int l0)
{
    q[0] = r1;
    int j, k, l1, front, rear;
    for (front=0, rear=0; front<=rear; front++) {
        j = ch[q[front]];
        while (j != -1) {
            q[++rear] = j;
            j = nx[j];
        }
    }
    re3(i, 0, rear) {
        j = q[i];
        for (int p=ed[j].next; p != j; p=ed[p].next) {
            k = ed[p].b;
            if (p != No && find(k) == r2) {
                l1 = ed[p].len - l0;
                if (l1 < res2) res2 = l1;
                del_edge(p);
            }
        }
    }
    u[r2] += u[r1]; u[r1] = r2; nx[r1] = ch[r2]; ch[r2] = r1;
}
void solve()
{
    int r1, r2, l0, num = 0;
    re(i, m2) {
        r1 = find(ed2[i].a); r2 = find(ed2[i].b);
        if (r1 != r2) {
            l0 = ed2[i].len; res1 += l0; num++;
            if (u[r1] >= u[r2]) uni(r1, r2, ed2[i].No, l0); else uni(r2, r1, ed2[i].No ^ 1, l0);
        }
    }
    if (num < n - 1) {res1 = res2 = -INF; return;}
    if (res2 == INF) res2 = -INF; else res2 += res1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res1 && res2 == INF) {
        prepare();
        solve();
    }
    pri();
    return 0;
}

KruskalO(M*(logN+logM))O(M)
PrimKruskal