BZOJ1977 次小生成树
题意是严格次小生成树。
想了一下发现应该是一条不在最小生成树上的边构成的环上替换一条边就行了。感觉好想noi那道lct，哈。其实不用那么复杂的。
就用倍增就可以了。不过我还是比较倾向于用链剖。感觉链剖空间小而且写起来倍爽。不像倍增写挂了不只一次了。
要注意的是不仅要找最大值还要找严格次大值，因为要找严格次小。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
struct edge_g {
int a, b, v, mk;
};
struct edge_t {
int t, v;
edge_t *next;
};
struct dat {
int a, b;
dat(int v0 = -1) {
a = v0, b = -1;
}
dat(int a0, int b0) {
a = a0, b = b0;
}
};
struct seg {
int l, r;
dat d;
seg *ls, *rs;
};
inline bool cmpEG(const edge_g& a, const edge_g& b) {
return a. v < b. v;
}
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 100009;
const int maxe = 300009;
int n, m, r[maxn];
edge_g g[maxe];
edge_t *head[maxn], *ep;
int d[maxn], fa[maxn], sz[maxn], fc[maxn], ch[maxn], cl[maxn], df[maxn], tc;
seg *rt[maxn], *sp;
int getRoot(int x) {
static int stc[maxn];
int tstc = 1;
stc[1] = x;
while (r[stc[tstc]] ^ stc[tstc])
stc[tstc + 1] = r[stc[tstc]], ++ tstc;
while (-- tstc)
r[stc[tstc]] = r[stc[tstc + 1]];
return r[x];
}
inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}
qw kruskal() {
qw s = 0;
ep = new edge_t[maxn * 2];
sort(g, g + m, cmpEG);
for (int i = 1; i <= n; ++ i)
r[i] = i;
for (int i = 0; i < m; ++ i)
if (getRoot(g[i]. a) ^ getRoot(g[i]. b)) {
addEdge(g[i]. a, g[i]. b, g[i]. v);
addEdge(g[i]. b, g[i]. a, g[i]. v);
g[i]. mk = 1;
s += g[i]. v;
r[getRoot(g[i]. a)] = getRoot(g[i]. b);
}
return s;
}
#define cpos(x) (d[x]-d[ch[fc[x]]])
#define mid(p) ((p->l+p->r)>>1)
inline dat ind(int v0) {
return dat(v0);
}
inline dat mkd(const dat& a, const dat& b) {
dat r;
if (a. a > b. a) {
r. a = a. a;
if (b. a == a. a)
r. b = max(a. b, b. b);
else
r. b = max(a. b, b. a);
}
else {
r. a = b. a;
if (b. b == a. a)
r. b = max(a. b, b. b);
else
r. b = max(a. a, b. b);
}
return r;
}
seg* sgtBuild(int l, int r) {
seg *p = sp ++;
p-> l = l;
p-> r = r;
if (l + 1 < r) {
p-> ls = sgtBuild(l, mid(p));
p-> rs = sgtBuild(mid(p), r);
}
return p;
}
void sgtChg(seg* p, int p0, int v0) {
if (p-> l + 1 == p-> r)
p-> d = ind(v0);
else {
if (p0 < mid(p))
sgtChg(p-> ls, p0, v0);
else
sgtChg(p-> rs, p0, v0);
p-> d = mkd(p-> ls-> d, p-> rs-> d);
}
}
dat sgtQry(seg* p, int l, int r) {
if (l >= r)
return dat();
else if (p-> l == l && p-> r == r)
return p-> d;
else if (r <= mid(p))
return sgtQry(p-> ls, l, r);
else if (l >= mid(p))
return sgtQry(p-> rs, l, r);
else
return mkd(sgtQry(p-> ls, l, mid(p)), sgtQry(p-> rs, mid(p), r));
}
void divide() {
static int q[maxn];
int hd = 0, tl = 1;
memset(d, 0, sizeof(d));
q[hd] = 1;
d[1] = 1;
while (hd < tl) {
int p = q[hd ++];
for (edge_t *e = head[p]; e; e = e-> next)
if (!d[e-> t]) {
d[e-> t] = d[p] + 1;
fa[e-> t] = p;
df[e-> t] = e-> v;
q[tl ++] = e-> t;
}
}
tc = 0;
for (int ti = tl - 1; ti >= 0; -- ti) {
int p = q[ti], fs = -1;
sz[p] = 1;
for (edge_t *e = head[p]; e; e = e-> next)
if (fa[e-> t] == p) {
sz[p] += sz[e-> t];
if (fs == -1 || sz[e-> t] > sz[fs])
fs = e-> t;
}
if (fs == -1) {
fc[p] = tc ++;
ch[fc[p]] = p;
cl[fc[p]] = 1;
}
else {
fc[p] = fc[fs];
ch[fc[p]] = p;
++ cl[fc[p]];
}
}
sp = new seg[maxn * 5];
for (int i = 0; i < tc; ++ i)
rt[i] = sgtBuild(0, cl[i]);
for (int p = 1; p <= n; ++ p)
sgtChg(rt[fc[p]], cpos(p), df[p]);
}
dat query(int u, int v) {
dat s;
while (fc[u] ^ fc[v])
if (d[ch[fc[u]]] > d[ch[fc[v]]]) {
s = mkd(s, sgtQry(rt[fc[u]], 0, cpos(u) + 1));
u = fa[ch[fc[u]]];
}
else {
s = mkd(s, sgtQry(rt[fc[v]], 0, cpos(v) + 1));
v = fa[ch[fc[v]]];
}
if (d[u] > d[v])
s = mkd(s, sgtQry(rt[fc[u]], cpos(v) + 1, cpos(u) + 1));
else if (d[v] > d[u])
s = mkd(s, sgtQry(rt[fc[v]], cpos(u) + 1, cpos(v) + 1));
return s;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(n);
readInt(m);
for (int i = 0; i < m; ++ i) {
readInt(g[i]. a);
readInt(g[i]. b);
readInt(g[i]. v);
g[i]. mk = 0;
}
qw v0 = kruskal();
divide();
int v1 = 0x3f3f3f3f;
for (int i = 0; i < m; ++ i)
if (!g[i]. mk) {
dat h = query(g[i]. a, g[i]. b);
if (g[i]. v > h. b && h. b > -1)
v1 = min(v1, g[i]. v - h. b);
if (g[i]. v > h. a && h. a > -1)
v1 = min(v1, g[i]. v - h. a);
}
printf(lld "\n", v0 + v1);
}
