TIOJ 1445 - 機器人組裝大賽

終於鼓起勇氣寫次小生成樹了
這題在解的時候有一筆一直過不了
後來才想到當邊的數量恰可構成一棵樹的時候不會有次小生成樹
然後再重讀題目時後發現如果無法構成次小生成樹時要輸出 -1
再不好好讀題目啊==

Description

給定 $N$ 個點, $M$ 條邊
輸出最小生成樹的花費跟次小生成樹的花費
如果無法構成,輸出 -1

Solution

這題的重點在次小生成樹的找法
簡單來說就是建完最小生成樹後,枚舉不在最小生成樹上的邊並加入它
加入它後,會形成一個環
把環上權重最大的邊拔掉即可
如此,即可找出最小生成樹

至於環上權重最大的邊的找法,使用的是 LCA 倍增法
建完祖先後即可 $O(\lg{n})$ 查詢了

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
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define MAXN 1005
#define MAXLG 12
#define ll long long

using namespace std;

struct Edge {
int u, v;
ll w;
bool vis;
bool operator < (const Edge &rhs) const {
return w < rhs.w;
}
};

struct DJS {
int par[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++)
par[i] = i;
}
int find(int n) {
return par[n] == n ? n : par[n] = find(par[n]);
}
void U(int a, int b) {
par[find(a)] = find(b);
}
bool is_same(int a, int b) {
return find(a) == find(b);
}
};

int n, m;
int par[MAXN][MAXLG];
ll dis[MAXN][MAXLG];
vector<Edge> E;
vector<pair<int, ll>> G[MAXN];
DJS djs;
int dep[MAXN];
ll mst, smst = LLONG_MAX;

bool Kruskal();
void dfs(int, int, ll);
ll lca(int, int);

signed main()
{
IO;
cin >> n >> m;
djs.init(n);
E.resize(m);
for (int i = 0; i < m; i++) {
cin >> E[i].u >> E[i].v >> E[i].w;
E[i].vis = false;
}
if (!Kruskal())
cout << "-1 -1" << endl;
else {
dfs(1, 0, 0);
for (auto &[u, v, w, f] : E)
if (!f)
smst = min(smst, mst + w - lca(u, v));
cout << mst << ' ' << (smst == LLONG_MAX ? -1 : smst) << endl;
}
return 0;
}

bool Kruskal()
{
int cnt = 0;
sort(E.begin(), E.end());
for (auto &[u, v, w, f] : E) {
if (cnt == n - 1)
break;
if (djs.is_same(u, v))
continue;
cnt++;
djs.U(u, v);
mst += w;
f = true;
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
return cnt == n - 1;
}

void dfs(int u, int f, ll l)
{
dep[u] = dep[f] + 1;
par[u][0] = f;
dis[u][0] = l;
for (int i = 1; i < MAXLG; i++) {
par[u][i] = par[par[u][i - 1]][i - 1];
dis[u][i] = max(dis[u][i - 1], dis[par[u][i - 1]][i - 1]);
}
for (auto &i : G[u])
if (i.first != f)
dfs(i.first, u, i.second);
}

ll lca(int u, int v)
{
if (u == v)
return 0LL;
if (dep[u] < dep[v])
swap(u, v);
ll res = 0LL;
for (int i = MAXLG - 1; i >= 0; i--)
if (dep[par[u][i]] >= dep[v])
res = max(res, dis[u][i]), u = par[u][i];
if (u == v)
return res;
for (int i = MAXLG - 1; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
res = max(res, max(dis[u][i], dis[v][i]));
u = par[u][i];
v = par[v][i];
}
}
return max(res, max(dis[u][0], dis[v][0]));
}