博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ 3669】 [Noi2014]魔法森林 LCT维护动态最小生成树
阅读量:5328 次
发布时间:2019-06-14

本文共 3704 字,大约阅读时间需要 12 分钟。

这道题看题意是在求一个二维最小瓶颈路,唯一可行方案就是枚举一维在这一维满足的条件下使另一维最小,那么我们就把第一维排序利用A小的边在A大的情况下仍成立来动态加边维护最小生成树。

#include 
#include
namespace Pre{ inline void read(int &sum){ register char ch=getchar(); for(sum=0;ch<'0'||ch>'9';ch=getchar()); for(;ch>='0'&&ch<='9';sum=(sum<<1)+(sum<<3)+ch-'0',ch=getchar()); } const int N=50010; const int M=100010; const int Inf=0x7f7f7f7f; int A[M],B[M],ans=Inf,X[M],Y[M],n,m,e[M]; inline bool comp(int a,int b){ return A[a]
y?x:y; } inline int Min(int x,int y){ return x
id]>B[ch[1]->id]?ch[0]->id:ch[1]->id; id=B[id]>B[rid]?id:rid; } inline void pushdown(); }null[MN]; inline void Swap(Node *&a,Node *&b){ Node *c=a; a=b; b=c; } inline void Node:: pushdown(){ if(!rev)return; Swap(ch[0],ch[1]); ch[0]->rev^=1; ch[1]->rev^=1; rev=0; } inline void Init(){ using namespace Pre; null->ch[0]=null->ch[1]=null->f=null; for(int i=1;i<=n;i++) null[i].ch[0]=null[i].ch[1]=null[i].f=null,null[i].id=null[i].rid=0; for(int i=n+1;i<=n+m;i++) null[i].ch[0]=null[i].ch[1]=null[i].f=null,null[i].id=null[i].rid=i-n; } inline int get(Node *p){ return p->f->ch[1]==p; } inline bool isroot(Node *p){ return p->f->ch[0]!=p&&p->f->ch[1]!=p; } inline void rotate(Node *p){ Node *fa=p->f,*pa=fa->f; int j=get(p); if(!isroot(fa))pa->ch[get(fa)]=p; if((fa->ch[j]=p->ch[j^1])!=null)fa->ch[j]->f=fa; fa->f=p; p->ch[j^1]=fa; p->f=pa; fa->pushup(); p->pushup(); } inline void spaly(Node *p){ p->pushdown(); for(Node *fa=p->f;!isroot(p);rotate(p),fa=p->f) if(!isroot(fa)){ fa->f->pushdown(),fa->pushdown(),p->pushdown(); rotate(get(fa)==get(p)?fa:p); }else fa->pushdown(),p->pushdown(); } inline void expose(Node *p){ Node *y=null; while(p!=null){ spaly(p); p->ch[1]=y; p->pushup(); y=p; p=p->f; } } inline void make_root(Node *p){ expose(p); spaly(p); p->rev^=1; } inline Node *find_root(Node *p){ expose(p); spaly(p); while(p->ch[0]!=null) p=p->ch[0],p->pushdown(); return p; } inline void link(Node *a,Node *b){ make_root(a); a->f=b; } inline void cut(Node *a,Node *b){ make_root(a); expose(b); spaly(b); b->ch[0]->f=null; b->ch[0]=null; b->pushup(); } inline void Link(int a,int b){ link(null+a,null+b); } inline void Cut(int a,int b){ cut(null+a,null+b); } inline int find(int x){ return find_root(null+x)-null; } inline int query(int a,int b){ Node *x=null+a,*y=null+b; make_root(x); expose(y); spaly(y); return Pre::B[y->id]; } inline int query_id(int a,int b){ Node *x=null+a,*y=null+b; make_root(x); expose(y); spaly(y); return y->id; }}inline void Init(){ using namespace Pre; read(n),read(m); for(int i=1;i<=m;i++) read(X[i]),read(Y[i]),read(A[i]),read(B[i]),e[i]=i; std::sort(e+1,e+m+1,comp); LCT::Init();}inline void Work(){ using namespace Pre; using LCT::find; using LCT::query; using LCT::Link; using LCT::Cut; using LCT::query_id; for(int i=1;i<=m;i++) if(find(X[e[i]])!=find(Y[e[i]])){ Link(e[i]+n,X[e[i]]),Link(e[i]+n,Y[e[i]]); if(find(1)==find(n)) ans=Min(query(1,n)+A[e[i]],ans); }else if(query(X[e[i]],Y[e[i]])>B[e[i]]){ int temp=query_id(X[e[i]],Y[e[i]]); Cut(temp+n,X[temp]),Cut(temp+n,Y[temp]); Link(e[i]+n,X[e[i]]),Link(e[i]+n,Y[e[i]]); if(find(1)==find(n)) ans=Min(ans,query(1,n)+A[e[i]]); }}int main(){ using namespace Pre; Init(),Work(); printf("%d",ans==Inf?-1:ans); return 0;}

 

转载于:https://www.cnblogs.com/TSHugh/p/7341114.html

你可能感兴趣的文章
我的PHP学习之路
查看>>
【题解】luogu p2340 奶牛会展
查看>>
对PostgreSQL的 SPI_prepare 的理解。
查看>>
解决响应式布局下兼容性的问题
查看>>
京东静态网页练习记录
查看>>
使用DBCP连接池对连接进行管理
查看>>
【洛谷】【堆+模拟】P2278 操作系统
查看>>
hdu3307 欧拉函数
查看>>
Spring Bean InitializingBean和DisposableBean实例
查看>>
Solr4.8.0源码分析(5)之查询流程分析总述
查看>>
[Windows Server]安装系统显示“缺少计算机所需的介质驱动程序”解决方案
查看>>
[容斥][dp][快速幂] Jzoj P5862 孤独
查看>>
Lucene 学习之二:数值类型的索引和范围查询分析
查看>>
软件开发工作模型
查看>>
Java基础之字符串匹配大全
查看>>
面向对象
查看>>
lintcode83- Single Number II- midium
查看>>
移动端 响应式、自适应、适配 实现方法分析(和其他基础知识拓展)
查看>>
selenium-窗口切换
查看>>
使用vue的v-model自定义 checkbox组件
查看>>