連結：https://tioj.ck.tp.edu.tw/problems/1445

題目大意

求連接所有元件的方法中，第一小與第二小的代價是多少，如果不存在輸出 −1。

題解

求最小生成樹與次小生成樹。最小生成樹很簡單，Kruskal 一下就好了，所以關鍵在如何求次小生成樹。

可以證明存在一個次小生成樹 T′ ，是最小生成樹 T 加上一條邊 e′ 之後，再將形成的環，刪除除了 e′ 之外的最長邊。

詳細演算法參考這邊：次小生成樹演算法與證明

要如何求一顆樹任兩點間的邊長的最大值呢？可以考慮 LCA的倍增法，在 dp 的同時，也記錄下目前區間的邊長最大值就好了。

該實作時間複雜度為 O(Elog⁡E+Elog⁡V)

AC 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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int N,M;
vector<tuple<int,ll>> V[1001];
vector<tuple<ll,int,int,bool>> E;

int dis[1001], groups;
void init(int n)
{
    for(int i=1;i<=n;++i)
        dis[i]=i;
    groups=n;
}
int find(int a)
{
    if( dis[a]==a ) return a;
    return dis[a]=find(dis[a]);
}
void U(int a,int b)
{
    dis[find(a)]=find(b);
    groups--;
}

ll mst()
{
    sort(E.begin(), E.end());
    init(N);
    ll ans=0;
    for(auto &[w,s,t,b]:E)
    {
        if( find(s)!=find(t) )
        {
            ans+=w;
            U(s,t);
            b=true;
            V[s].emplace_back(t,w);
            V[t].emplace_back(s,w);
        }
    }
    if( groups==1 ) return ans;
    return -1;
}

const int lgN = 11;
int dp[1001][lgN];
ll mx[1001][lgN];
ll dep[1001];

void dfs(int v, int fa, int ew)
{
    dp[v][0]=fa;
    mx[v][0]=ew;
    for(auto [e,w]:V[v])
    {
        if( e==fa ) continue;
        dep[e]=dep[v]+1;
        dfs(e, v, w);
    }
}

void build()
{
    dep[1]=0;
    dfs(1, -1, 0);
    for(int i=0;i<lgN-1;++i)
        for(int j=1;j<=N;++j)
        {
            mx[j][i+1] = mx[j][i];
            if( dp[j][i+1]==-1 ) dp[j][i] = -1;
            else {
                mx[j][i+1] = max( mx[j][i+1], mx[dp[j][i]][i] );
                dp[j][i+1] = dp[dp[j][i]][i];
            }
        }
}

int jump(int v, int d, ll &ans)
{
    for(int i=0;i<lgN;++i)
    {
        if( (d>>i)&1 )
        {
            ans=max(ans, mx[v][i]);
            v=dp[v][i];
        }
    }
    return v;
}

ll path(int s, int e)
{
    ll ans = 0;
    if( dep[s]<dep[e] ) swap(s,e);
    s = jump( s, dep[s]-dep[e], ans);
    if( s!=e )
    {
        for(int i=lgN-1;i>=0;--i)
        {
            if( dp[s][i]!=dp[e][i] )
            {
                ans = max( ans, mx[s][i] );
                ans = max( ans, mx[e][i] );
                s = dp[s][i];
                e = dp[e][i];
            }
        }
        ans = max({ans, mx[s][0], mx[e][0]});
    }
    return ans;
}

ll smst(ll mstw)
{
    if( (int)E.size() == N-1 ) return -1;
    build();
    ll ans = LLONG_MAX;
    ll tmp;
    
    for(auto &[w,s,t,b]:E)
    {
        if(b) continue;
        tmp = path(s,t);
        ans = min( ans, mstw-tmp+w );
    }

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N>>M;
    int s,t;
    ll w, ans1, ans2;
    while(M--)
    {
        cin>>s>>t>>w;
        E.emplace_back(w,s,t,false);
    }

    ans1 = mst();
    if( ans1 == -1 ) ans2 = -1;
    else ans2 = smst(ans1);

    cout<<ans1<<' '<<ans2<<'\n';
}