首先问个问题，都已经 ```define int long long``` 了为什么还有个 ```long long cal```
by Frozen_Ladybug @ 2024-02-08 12:57:32
@[Frozen_Ladybug](/user/384719) 改成这样，70分了。
```cpp
#include <bits/stdc++.h>
#define MAXN 100007
#define MAXM 300007
#define int long long
using namespace std;
struct edge {
int nxt, to, val;
} e[MAXN << 1]; int h[MAXN], cnt;
void add(int u, int v, int w) {
e[++cnt].nxt = h[u]; e[cnt].to = v; e[cnt].val = w; h[u] = cnt;
}
struct edge1 {
int u, v, w;
bool used;
} e1[MAXN << 1];
int n, m, fa[MAXN], ans0;
bool cmp(edge1 a, edge1 b) {
return a.w < b.w;
}
int find(int x) {
if(x != fa[x]) return fa[x] = find(fa[x]);
else return x;
}
void kruskal() {
sort(e1 + 1, e1 + m + 1, cmp);
for(int i = 1; i <= m; i++) {
int u = find(e1[i].u), v = find(e1[i].v);
if(u == v) continue;
ans0 += e1[i].w;
add(e1[i].u, e1[i].v, e1[i].w); add(e1[i].v, e1[i].u, e1[i].w);
e1[i].used = 1; fa[v] = u;
}
}
int f[MAXN][20], mx[MAXN][20], mx2[MAXN][20], dep[MAXN];
void dfs(int u) {
dep[u] = dep[f[u][0]] + 1;
for(int i = 1; i <= 19; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
if(mx[u][i - 1] == mx[f[u][i - 1]][i - 1]) {
mx[u][i] = mx[u][i - 1];
mx2[u][i] = max(mx2[f[u][i - 1]][i - 1], mx2[u][i - 1]);
}
if(mx[u][i - 1] > mx[f[u][i - 1]][i - 1]) {
mx[u][i] = mx[u][i - 1];
mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[u][i - 1]);
}
if(mx[f[u][i - 1]][i - 1] > mx[u][i - 1]) {
mx[u][i] = mx[f[u][i - 1]][i - 1];
mx2[u][i] = max(mx[u][i - 1], mx2[f[u][i - 1]][i - 1]);
}
}
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to, w = e[i].val;
if(v == f[u][0]) continue;
f[v][0] = u; mx[v][0] = w; dfs(v);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = 19; i >= 0; i--)
if(dep[u] - dep[v] >= (1 << i)) u = f[u][i];
if(u == v) return u;
for(int i = 19; i >= 0; i--) {
if(f[u][i] != f[v][i]) {
u = f[u][i]; v = f[v][i];
}
}
return f[u][0];
}
int cal(int u, int v, int w) {
int l = lca(u, v);
int nmx = 0, nmx2 = 0;
for(int i = 19; i >= 0; i--) {
if(dep[f[u][i]] >= dep[l]) {
if(nmx == mx[u][i]) nmx2 = max(mx2[u][i], nmx2);
if(nmx > mx[u][i]) nmx2 = max(mx[u][i], nmx2);
if(nmx < mx[u][i]) {
nmx2 = max(mx2[u][i], nmx); nmx = mx[u][i];
}
u = f[u][i];
}
if(dep[f[v][i]] >= dep[l]) {
if(nmx == mx[v][i]) nmx2 = max(mx2[v][i], nmx2);
if(nmx > mx[v][i]) nmx2 = max(mx[v][i], nmx2);
if(nmx < mx[v][i]) {
nmx2 = max(mx2[v][i], nmx); nmx = mx[v][i];
}
v = f[v][i];
}
}
if(w != nmx) return ans0 - nmx + w;
if(nmx2) return ans0 - nmx2 + w;
return LONG_LONG_MAX;
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> e1[i].u >> e1[i].v >> e1[i].w;
for(int i = 1; i <= n; i++) fa[i] = i;
kruskal();
dfs(1);
int ans = LONG_LONG_MAX;
for(int i = 1; i <= m; i++)
if(!e1[i].used)
ans = min(cal(e1[i].u, e1[i].v, e1[i].w), ans);
cout << ans;
return 0;
}
```
by littlesnake @ 2024-02-08 13:03:55
@[Frozen_Ladybug](/user/384719) 又改成这样，93分了。
```cpp
#include <bits/stdc++.h>
#define MAXN 100007
#define MAXM 300007
#define int long long
using namespace std;
struct edge {
int nxt, to, val;
} e[MAXM << 1]; int h[MAXN], cnt;
void add(int u, int v, int w) {
e[++cnt].nxt = h[u]; e[cnt].to = v; e[cnt].val = w; h[u] = cnt;
}
struct edge1 {
int u, v, w;
bool used;
} e1[MAXM << 1];
int n, m, fa[MAXN], ans0;
bool cmp(edge1 a, edge1 b) {
return a.w < b.w;
}
int find(int x) {
if(x != fa[x]) return fa[x] = find(fa[x]);
else return x;
}
void kruskal() {
sort(e1 + 1, e1 + m + 1, cmp);
for(int i = 1; i <= m; i++) {
int u = find(e1[i].u), v = find(e1[i].v);
if(u == v) continue;
ans0 += e1[i].w;
add(e1[i].u, e1[i].v, e1[i].w); add(e1[i].v, e1[i].u, e1[i].w);
e1[i].used = 1; fa[v] = u;
}
}
int f[MAXN][20], mx[MAXN][20], mx2[MAXN][20], dep[MAXN];
void dfs(int u) {
dep[u] = dep[f[u][0]] + 1;
for(int i = 1; i <= 19; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
if(mx[u][i - 1] == mx[f[u][i - 1]][i - 1]) {
mx[u][i] = mx[u][i - 1];
mx2[u][i] = max(mx2[f[u][i - 1]][i - 1], mx2[u][i - 1]);
}
if(mx[u][i - 1] > mx[f[u][i - 1]][i - 1]) {
mx[u][i] = mx[u][i - 1];
mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[u][i - 1]);
}
if(mx[f[u][i - 1]][i - 1] > mx[u][i - 1]) {
mx[u][i] = mx[f[u][i - 1]][i - 1];
mx2[u][i] = max(mx[u][i - 1], mx2[f[u][i - 1]][i - 1]);
}
}
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to, w = e[i].val;
if(v == f[u][0]) continue;
f[v][0] = u; mx[v][0] = w; dfs(v);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(int i = 19; i >= 0; i--)
if(dep[u] - dep[v] >= (1 << i)) u = f[u][i];
if(u == v) return u;
for(int i = 19; i >= 0; i--) {
if(f[u][i] != f[v][i]) {
u = f[u][i]; v = f[v][i];
}
}
return f[u][0];
}
int cal(int u, int v, int w) {
int l = lca(u, v);
int nmx = 0, nmx2 = 0;
for(int i = 19; i >= 0; i--) {
if(dep[f[u][i]] >= dep[l]) {
if(nmx == mx[u][i]) nmx2 = max(mx2[u][i], nmx2);
if(nmx > mx[u][i]) nmx2 = max(mx[u][i], nmx2);
if(nmx < mx[u][i]) {
nmx2 = max(mx2[u][i], nmx); nmx = mx[u][i];
}
u = f[u][i];
}
if(dep[f[v][i]] >= dep[l]) {
if(nmx == mx[v][i]) nmx2 = max(mx2[v][i], nmx2);
if(nmx > mx[v][i]) nmx2 = max(mx[v][i], nmx2);
if(nmx < mx[v][i]) {
nmx2 = max(mx2[v][i], nmx); nmx = mx[v][i];
}
v = f[v][i];
}
}
if(w != nmx) return ans0 - nmx + w;
if(nmx2) return ans0 - nmx2 + w;
return LONG_LONG_MAX;
}
signed main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) cin >> e1[i].u >> e1[i].v >> e1[i].w;
for(int i = 1; i <= n; i++) fa[i] = i;
kruskal();
dfs(1);
int ans = LONG_LONG_MAX;
for(int i = 1; i <= m; i++)
if(!e1[i].used)
ans = min(cal(e1[i].u, e1[i].v, e1[i].w), ans);
cout << ans;
return 0;
}
```
by littlesnake @ 2024-02-08 13:05:37