其实这道题大概是一两周之前的考试题, 还是我之前做过的题.
不过考试的时候50分和100分的做法都写跪了, 考试后也没有调出来.
来填坑了.
Bugs
大概知道我考试时代码最大的bug是啥了.
需要维护的是最大边和次大边, 但是我好像维护的是最小边和次小边.
能得分才见鬼了
昨天做的时候制造了很多bug, 捡其中最sb的几个来说一下
- 上面讲了
- 倍增维护了向上跳跳到那个位置和路径最大次大值, 我是先跳了之后再求的最大次大值.这样还有70分数据是真的水.
- 去重里面加了个
greater<int>()导致去重失败, 90分, 数据是真的水.
优化
把程序写对了之后, 发现开O2优化能过（而且很快）, 不开就超时了, 原因大概是我用了太多的STL里面的东西, 如vector<int>, pair<int, int>, 众所周知, 因为STL使用模板元的缘故, 效率是相当的感动.
于是替换成数组和简陋的手写小结构, 通过.
然后又把合并两个最大值, 次大值的函数替换成运算符+=, +, 并且使用了switch避免了贼慢的分支结构.
然后就卡到了599ms.
真劲呢.
然后就为了优化寻址, 把f(向上跳跳到那个位置)和g(路径最大次大值)合并成一个结构.
反而变慢了一点. 也许是.....的原因吧.
final code
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100005;
const int M = 300005;
const long long inf_ll = 1e15;
const int MAXIN = 300000;
char IN[MAXIN], *SS = IN, *TT = IN;
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
// #define gc() getchar()
inline int read() {
int now = 0; register char c = gc();
for (; !isdigit(c); c = gc());
for (; isdigit(c); now = now * 10 + c - '0', c = gc());
return now;
}
using std:: min;
using std:: max;
struct Pair {
int first, second, third;
Pair() {}
Pair(int _, int __) : first(_), second(__) { }
Pair(int _, int __, int ___) : first(_), second(__), third(___) { }
Pair operator + (const Pair& o) const {
switch(first == o.first ? 0 : (first > o.first ? 1 : -1)) {
case 1:
return Pair(first, max(o.first, second), o.third); break;
case -1:
return Pair(o.first, max(first, o.second), o.third); break;
default:
return Pair(first, max(second, o.second), o.third);
}
}
void operator += (const Pair& o) {
switch(first == o.first ? 0 : (first > o.first ? 1 : -1)) {
case 1:
second = max(second, o.first); break;
case -1:
second = max(first, o.second); first = o.first; break;
default:
second = max(second, o.second);
}
}
};
class Graph {
struct Edge {
int v, c; Edge* nxt;
Edge(int _, int __, Edge* ___) : v(_), c(__), nxt(___) {}
} *head[N];
int n;
int dep[N];
Pair g[N][17];
void dfs(int u, int fa) {
dep[u] = dep[fa] + 1;
for (auto edge = head[u]; edge; edge = edge->nxt) {
int v = edge->v; if (v == fa) continue;
g[v][0] = Pair(edge->c, -1, u);
dfs(v, u);
}
}
public:
Graph(int _) : n(_) {}
void AddEdge(int _, int __, int ___) {
head[_] = new Edge(__, ___, head[_]);
head[__] = new Edge(_, ___, head[__]);
}
void init() {
g[1][0] = Pair(-1, -1, 0);
dfs(1, 0);
for (int i = 1; i < 17; i += 1)
for (int j = 1; j <= n; j += 1)
g[j][i] = g[j][i - 1] + g[g[j][i - 1].third][i - 1];
}
Pair lca(int u, int v) {
if (dep[u] < dep[v]) std :: swap(u, v);
if (v == g[u][0].third) return Pair(-1, -1);
Pair res = Pair(-1, -1);
for (int i = 16; ~i; i -= 1)
if (dep[g[u][i].third] >= dep[v]) {
res += g[u][i], u = g[u][i].third;
}
for (int i = 16; ~i; i -= 1)
if (g[u][i].third != g[v][i].third)
res += g[u][i] + g[v][i],
u = g[u][i].third, v = g[v][i].third;
return u == v ? res : res + g[u][0] + g[v][0];
}
};
class Solution {
private:
int n, m;
int find(int u) { return u == f[u] ? u : f[u] = find(f[u]); }
struct Edge {
int u, v, c;
bool operator < (const Edge& o) const {
return c < o.c;
}
Edge() {}
Edge(int p) : u(read()), v(read()), c(read()) { }
};
Graph* G;
Edge edge[M];
int f[N], vis[M];
long long Val;
public:
Solution(int _, int __) : n(_), m(__) { }
void init() {
G = new Graph(n);
for (int i = 0; i < m; i += 1)
edge[i] = Edge(1);
std:: sort(edge, edge + m);
for (int i = 1; i <= n; i += 1) f[i] = i;
int rd = 0; Val = 0;
for (int i = 0; i < m and rd < n; i += 1) {
Edge* e = &edge[i];
int fu = find(e->u), fv = find(e->v);
if (fu != fv)
f[fu] = fv, rd += 1, Val += 1ll * e->c,
G->AddEdge(e->u, e->v, e->c), vis[i] = true;
else vis[i] = false;
}
G->init();
}
long long getans() {
long long Res = inf_ll;
for (int i = 0; i < m; i += 1)
if (not vis[i]) {
auto e = &edge[i];
int u = e->u, v = e->v, c = e->c;
Pair p = G->lca(u, v);
if (p.first == c) {
if (~p.second) Res = std:: min(Res, Val + c - p.second);
} else Res = std:: min(Res, Val + c - p.first);
}
return Res;
}
};
int main () {
int n = read(), m = read();
Solution* Sol = new Solution(n, m);
Sol->init();
std:: cout << Sol->getans();
return 0;
}