P4180严格次小生成树

Posted on Edited on In Word count in article: 846 Reading time ≈ 3 mins.
图论，次小生成树

P4180 [BJWC2010]严格次小生成树

题意同标题

最小生成树就不用说了, 那么次小生成树就是枚举剩下的边, 把它加入到我们的最小生成树中, 这样就构成了一个奇环树, 考虑这条新加入的边能够取代哪一条边, 能使新生成的树为一颗与原来全职不相等的树?

显然答案是取代第一个长度严格小于新加入的边的那一条, 关于这一条边, 我们可以维护树上两点间的最大边权和严格次大边权

因为做这道题时, 没发现写树剖维护的, 觉得倍增写着挺好看的, 于是就写了个倍增维护的

Code

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 <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Maxn = 1e5 + 10, Maxm = 3e5 + 10;
int N, M, MinInc(1e9 + 10);
int F[Maxn][20], Max[Maxn][20], SMax[Maxn][20];
int Depth[Maxn], Fa[Maxn];
int Head[Maxn], E[Maxm << 1], Next[Maxm << 1], Cost[Maxm << 1], Cur;
ll Ans;

struct Node
{
    int U, V, W;
    bool In;
    bool operator < (const Node &Temp) const 
    {
        return W < Temp.W;
    }
}_E[Maxm];

int Find(int X)
{
    if (Fa[X] == X) return X;
    return Fa[X] = Find(Fa[X]);
}

inline void AddEdge(int U, int V, int W)
{
    Next[++Cur] = Head[U];
    Head[U] = Cur;
    E[Cur] = V;
    Cost[Cur] = W;
}

inline void MST(int Cnt = 0)
{
    for (int i = 1; i <= N; ++i) Fa[i] = i;
    for (int i = 1; Cnt != N - 1; ++i)
    {
        int U = _E[i].U, V = _E[i].V, FU = Find(U), FV = Find(V);
        if (FU == FV) continue;
        Fa[FV] = FU;
        ++Cnt;
        _E[i].In = 1;
        Ans += _E[i].W;
        AddEdge(U, V, _E[i].W);
        AddEdge(V, U, _E[i].W);//建边
    }
}//最小生成树

void DFS(int X, int _f, int WEdge, int Dep)
{
    Depth[X] = Dep, F[X][0] = _f, Max[X][0] = WEdge, SMax[X][0] = -1; 
    for (int i = 1; (1 << i) <= Dep; ++i)
    {
        F[X][i] = F[F[X][i - 1]][i - 1];
        Max[X][i] = max(Max[X][i - 1], Max[F[X][i - 1]][i - 1]);//倍增维护最大的边
        SMax[X][i] = max(SMax[X][i - 1], SMax[F[X][i - 1]][i - 1]);//次大
        if (Max[X][i - 1] < Max[X][i]) SMax[X][i] = max(SMax[X][i], Max[X][i - 1]);
        else if (Max[X][i - 1] > Max[F[X][i - 1]][i - 1]) SMax[X][i] = max(SMax[X][i], Max[F[X][i - 1]][i - 1]);
    }
    for (int i = Head[X]; i; i = Next[i])
    {
        int V = E[i];
        if (V == _f) continue;
        DFS(V, X, Cost[i], Dep + 1);
    }
}

inline int LCA(int X, int Y)
{
    if (Depth[X] < Depth[Y]) X ^= Y ^= X ^= Y;
    int K = Depth[X] - Depth[Y];
    for (int i = 0; i <= 17; ++i)
        if (K >> i & 1) X = F[X][i];
    if (X == Y) return X;
    for (int i = 17; i >= 0; --i)
        if (F[X][i] != F[Y][i]) X = F[X][i], Y = F[Y][i];
    return F[X][0];
}

inline void Work(int S, int T, int _W)
{
    int Ans(0), K = Depth[S] - Depth[T];
    for (int i = 0; i <= 17; ++i)
        if (K >> i & 1)
        {
            if (Max[S][i] != _W) Ans = max(Ans, Max[S][i]);
            else Ans = max(Ans, SMax[S][i]);
            S = F[S][i];
        }//找路径上严格小于_W的最大边
    MinInc = min(MinInc, _W - Ans);
}

int main()
{
    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i) scanf ("%d %d %d", &_E[i].U, &_E[i].V, &_E[i].W);
    sort (_E + 1, _E + M + 1);
    MST();
    DFS(1, 0, 0, 1);
    for (int i = 1; i <= M; ++i)
        if (!_E[i].In)
        {
            int U = _E[i].U, V = _E[i].V;
            int Lca = LCA(U, V);
            Work (U, Lca, _E[i].W);
            Work (V, Lca, _E[i].W);
        }
    printf ("%lld\n", Ans + MinInc);//答案是最小生成树+最小增量
    system ("pause");
}

若这道题求的并不是严格次小生成树, 那么就不需要维护次小边, 就是说最小增量可能为零

多说一句, 洛谷的数据貌似真的太弱了, 我有地方写挂了竟然都可以\(AC\)

而且洛谷评测的速度比\(LOJ\)慢太多啦