2018-01-18 15:44:37

实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e4, MAXM = 1e5;

//----------------LCT--------------------
struct Node *null, *nd[MAXN+10];
struct Node {
int v, s, maxv; bool flip;
Node *fa, *ch[2];
Node() { v = maxv = 0; s = 1; flip = false; fa = ch[0] = ch[1] = null; }
Node(int v_) { v = maxv = v_; s = 1; flip = false; fa = ch[0] = ch[1] = null; }
bool splayrt() { return fa->ch[0]!=this && fa->ch[1]!=this; }
int rel() { return splayrt() ? -1 : (fa->ch[0]==this ? 0 : 1); }
void rev() { flip^=1; }
int cmp(int k) { return k == ch[0]->s + 1 ? -1 : (k > ch[0]->s + 1 ? 1 : 0); }
void pushdown() {
if(flip) {
flip^=1; ch[0]->flip^=1; ch[1]->flip^=1;
swap(ch[0], ch[1]);
}
}
void maintain() {
maxv = max(max(ch[0]->maxv, ch[1]->maxv), v);
s = ch[0]->s + ch[1]->s + 1;
}
};

void init_null() {
null = new Node(0); null->s = 0;
}

void rotate(Node* o) {
Node *x, *y, *k; int d, d2;
if(o->splayrt()) return;
x = o->fa; y = x->fa;
d = o->rel(); d2 = x->rel();
k = o->ch[d^1];
if(!x->splayrt()) y->ch[d2] = o;
o->fa = y;
o->ch[d^1] = x; x->fa = o;
x->ch[d] = k; k->fa = x;
x->maintain(); o->maintain();
}

void Splay(Node* o) {
static Node *x, *S[(MAXN<<1)+10]; int p, d, d2;
for(p=1, S[p] = o; !S[p]->splayrt(); p++)
S[p+1] = S[p]->fa;
for(; p; p--) S[p]->pushdown();
while(!o->splayrt()) {
x = o->fa;
d = o->rel(); d2 = x->rel();
if(!x->splayrt()) {
if(d == d2) rotate(x);
else rotate(o);
}
rotate(o);
}
}

Node* FindMax(Node* o) {
if(o->v == o->maxv) //!!
return o;
else return o->ch[0]->maxv == o->maxv ?
FindMax(o->ch[0]) : FindMax(o->ch[1]);
}

Node* Kth(Node* o, int k) {
if(o == null) return o;
int d = o->cmp(k);
if(d==-1) return o;
return Kth(o->ch[d], k - d*(o->ch[0]->s + 1));
}

void Access(Node* o) {
for(Node *t=null; o!=null; t=o, o=o->fa) {
Splay(o); o->ch[1] = t; o->maintain();
}
}

void MakeRoot(Node* o) {
Access(o); Splay(o); o->rev();
}

Node* GetRoot(Node* o) {
Access(o); Splay(o);
while(o->ch[0] != null) o = o->ch[0];
return o;
}

void Link(Node* u, Node* v) {
if(GetRoot(u) == GetRoot(v)) return;
MakeRoot(u); Splay(u); u->fa = v;
}

void Cut(Node* u, Node* v) {
if(GetRoot(u) != GetRoot(v)) return;
MakeRoot(u); Access(v); Splay(u);
if(u->ch[1] == v) {
u->ch[1] = null; v->fa = null;
u->maintain();
}
}

//-----------------------------------------

struct Edge {
int u, v, a, b;
Edge() {}
Edge(int u_, int v_, int a_, int b_):
u(u_), v(v_), a(a_), b(b_) {}
inline bool operator<(const Edge& rhs) const
{ return a < rhs.a; }
} E[MAXM+10];
int N, M, Ans, fa[MAXN+10];

int GetFather(int x) { return fa[x] == x ? x : fa[x] = GetFather(fa[x]); }
inline void Union(int x, int y) { fa[GetFather(x)] = GetFather(y); }

template<typename T>
inline void readint(T& x) {
T f=1, r=0; char c=getchar();
while(!isdigit(c)){ if(c=='-')f=-1; c=getchar(); }
while(isdigit(c)){ r=r*10+c-'0'; c=getchar(); }
x = f*r;
}

void Init() {
int u, v, a, b;
init_null();
readint(N); readint(M);
for(int i=1; i<=N; i++) {
nd[i] = new Node(0);
fa[i] = i;
}
for(int i=1; i<=M; i++) {
readint(u); readint(v);
readint(a); readint(b);
E[i] = Edge(u, v, a, b);
}
sort(E+1, E+M+1);
}

inline void AddTreeEdge(int u, int v, int b) {
Node* w = new Node(b);
Link(nd[u], w); Link(nd[v], w);
if(GetFather(u) != GetFather(v))
Union(u, v);
}

inline Node* GetMaxEdge(int u, int v) {
Node* w;
MakeRoot(nd[u]); Access(nd[v]); Splay(nd[u]);
w = FindMax(nd[u]);
Splay(w);
return w;
}

inline void CutMaxEdge(int u, int v) {
Node *w, *x, *y; int k;
w = GetMaxEdge(u, v); k = w->ch[0]->s + 1;
x = Kth(w, k-1); y = Kth(w, k+1);
if(x == null || y == null) return;
Cut(w, x); Cut(w, y);
}

void Work() {
int u, v, a, b; bool add = false;
Ans = INT_MAX;
for(int t=1; t<=M; t++) {
u = E[t].u, v = E[t].v, a = E[t].a, b = E[t].b;
add = false;
if(GetFather(u) != GetFather(v))
add = true, AddTreeEdge(u, v, b);
else if(b < GetMaxEdge(u, v)->v) {
add = true;
CutMaxEdge(u, v);
AddTreeEdge(u, v, b);
}
//更新答案
if(add && GetFather(1) == GetFather(N))
Ans = min(Ans, a + GetMaxEdge(1, N)->v);
}
if(Ans < INT_MAX)
printf("%d", Ans);
else puts("-1");
}

int main() {
Init(); Work();
return 0;
}
• star
首页