以前一直觉得lct特别难写,自从学了丽洁姐的lct之后,觉得lct居然能这么短,这个主程序能40行左右解决~~~~
这道嘛~~虽说能用spfa解决,但还是写下lct吧
把边按a值排序后一条一条插入并维护bmx值就行了= =
不过还是得膜拜云神在考场上a了这道题,我花了好久,自己还是太弱
NOIP就要来了,在这里祝自己RP++吧
毕竟升高二后,每天几乎都是怀着梦想睡觉的
希望这一年能不辜负我的愿望吧
向着最高点,冲吧!!!
CODE:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define maxn 101000
struct node{
node *ch[2],*p,*mx;bool rec;int val;
node(int v=0):val(v) {
rec=false;
p=ch[0]=ch[1]=NULL;
mx=this;
}
inline bool d();
inline bool isroot();
inline void update();
inline void relax();
}t[maxn];
inline bool node::d(){return p->ch[1]==this;}
inline bool node::isroot(){
return (p==NULL)||(p->ch[1]!=this&&p->ch[0]!=this);
}
inline void node::relax(){
if (!this) return;
if (!rec) return ;
if (ch[1]) ch[1]->rec^=1;
if (ch[0]) ch[0]->rec^=1;
swap(ch[1],ch[0]);
rec=0;
}
inline void node::update(){
if (!this) return ;
mx=this;
if (ch[0]&&ch[0]->mx->val > mx->val ) mx=ch[0]->mx;
if (ch[1]&&ch[1]->mx->val > mx->val ) mx=ch[1]->mx;
}
inline void rotate(node*u) {
node *v=u->p;
v->relax();u->relax();
bool d=u->d();
if (!v->isroot()) v->p->ch[v->d()]=u;
u->p=v->p;
if (u->ch[d^1]) u->ch[d^1]->p=v;
v->ch[d]=u->ch[d^1];
u->ch[d^1]=v;
v->p=u;
v->update(),u->update();
}
inline void splay(node *u) {
u->relax();
while (!u->isroot()){
if (u->p->isroot()) rotate(u);
else if (u->d()!=u->p->d()) rotate(u),rotate(u);
else rotate(u->p),rotate(u);
}
u->update();
}
inline node* expose(node *u) {
node *v;
for (v=NULL;u;v=u,u=u->p){
splay(u);
u->ch[1]=v;
u->update();
}
return v;
}
inline void evert(node *u) {
expose(u)->rec^=1;
splay(u);
}
inline void link(node *u,node *v) {
evert(u);
u->p=v;
expose(u);
}
inline void cut(node *u,node *v) {
evert(u);
expose(v);
splay(v);
v->ch[0]=u->p=NULL;
v->update();u->update();
}
inline int query(node *u,node *v) {
evert(u);
expose(v);
splay(v);
return v->mx->val;
}
int fa[maxn];
inline int find(int x) {
if (fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int x[maxn],y[maxn],a[maxn],b[maxn],id[maxn];
bool cmp(int p,int q) {return a[p]<a[q];}
map<node*,int> ma;
int n,m;
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++) {
scanf("%d%d%d%d",x+i,y+i,a+i,b+i);
id[i]=i;
}
sort(id+1,id+1+m,cmp);
int ans=0x7fffffff;
for (int i=1;i<=m;i++) {
if (x[id[i]]==y[id[i]]) continue;
node *u=&t[x[id[i]]],*v=&t[y[id[i]]];
if (find(x[id[i]])!=find(y[id[i]])) {
node *e=new node(b[id[i]]);
ma[e]=id[i];
link(u,e);
link (v,e);
fa[find(x[id[i]])]=find(y[id[i]]);
}else {
evert(u);
expose(v);
splay(v);
if (v->mx->val>b[id[i]]){
node *e=v->mx;
splay(e);
node *_u=&t[x[ma[e]]],*_v=&t[y[ma[e]]];
cut(e,_u);
cut(e,_v);
delete e;
e=new node(b[id[i]]);
ma[e]=id[i];
link (u,e);
link (v,e);
}
}
if (find(1)==find(n)) ans=min(ans,a[id[i]]+query(&t[1],&t[n]));
}
if (ans==0x7fffffff) ans=-1;
printf("%d\n",ans);
return 0;
}