基本思路:
首先按照weightA升序排序,然后依次在图中加边,并维护起点到终点路径上weightB的最大值
如果加边过程中生成了环,则删除环中weightB最大的边
由于是无向图,点之间没有拓扑序,所以在建立LCT模型时,可以将原图的边也视为点,这样就转化成了维护路径上的点权最大值(Orz Hzwer)
点的连通性可以用并查集维护
AC code:(其实Splay双旋一次时只需要进行3次update,而代码中舍弃了这个优化)
#include <cstdio> #include <cstring> #include <algorithm> ; ; const int inf=0x3f3f3f3f; struct Edge { int u,v; int weightA,weightB; void assign(int _u,int _v,int _wa,int _wb) { u=_u; v=_v; weightA=_wa; weightB=_wb; } bool operator < (const Edge& other) const { return this->weightA < other.weightA; } }; Edge elist[maxM]; inline int getMaxIdx(int u,int v) { return elist[u].weightB > elist[v].weightB ? u : v; } //Let elist[0].weightB = -inf struct Splay { int idx; int maxIdx; bool rev; Splay* child[]; Splay* parent; void init(int id) { idx=maxIdx=id; rev=false; child[]=child[]=parent=; } bool isRoot() { if(!parent) return true; ] && ]; } void update() { maxIdx=idx; ]) maxIdx=getMaxIdx(]->maxIdx); ]) maxIdx=getMaxIdx(]->maxIdx); } void reverse() { if(!isRoot()) parent->reverse(); if(rev) { std::swap(child[],child[]); ]) child[]->rev ^= ; ]) child[]->rev ^= ; ; } } ; } void rotate(int dir) { Splay* temp=parent; this->parent=temp->parent; if(parent) { ]) parent->child[]=this; ]) parent->child[]=this; } temp->child[dir^]=this->child[dir]; if(child[dir]) child[dir]->parent=temp; child[dir]=temp; temp->parent=this; temp->update(); this->update(); } void splay() { reverse(); while(!isRoot()) { ); ]) st|=; ; if(!parent->isRoot()) { ]) st|=; ; } switch(st) { : rotate(); break; : rotate(); break; : parent->rotate(); ); break; : rotate(); rotate(); break; : rotate(); rotate(); break; :parent->rotate(); ); break; } } } }; Splay node[maxN+maxM]; int access(int idx) { Splay *cur,*last; ;cur;last=cur,cur=cur->parent) { cur->splay(); cur->child[]=last; cur->update(); } return last->maxIdx; } inline void setAsRoot(int idx) { access(idx); node[idx].splay(); node[idx].setRev(); } inline void link(int u,int v) { setAsRoot(u); node[u].parent=node+v; } inline void cut(int u,int v) { setAsRoot(u); access(v); node[v].splay(); node[v].child[]=node[u].parent=; node[v].update(); } inline int query(int u,int v) { setAsRoot(u); return access(v); } int N,M; int center[maxN]; int getCenter(int idx) { return center[idx]==idx ? idx : center[idx]=getCenter(center[idx]); } void input() { scanf("%d%d",&N,&M); int u,v,wa,wb; ;i<=M;i++) { scanf("%d%d%d%d",&u,&v,&wa,&wb); if(u==v) { --i; --M; } else elist[i].assign(u,v,wa,wb); } } void init() { elist[].weightB=-inf; std::sort(elist+,elist+M+); ;i<=M;i++) node[i].init(i); ;i<=N;i++) node[i+M].init(); ;i<=N;i++) center[i]=i; } void addEdge(int e) { int& u=elist[e].u; int& v=elist[e].v; int cu=getCenter(u); int cv=getCenter(v); if(cu!=cv) { link(e,M+u); link(e,M+v); center[cu]=cv; } else { int mx=query(M+u,M+v); if(elist[e].weightB < elist[mx].weightB) { cut(mx,M+elist[mx].u); cut(mx,M+elist[mx].v); link(e,M+u); link(e,M+v); } } } int solve() { int ans(inf); init(); ;i<=M;i++) { addEdge(i); )==getCenter(N)) { ,M+N); ans=std::min(ans,elist[i].weightA+elist[mx].weightB); } } :ans; } int main() { input(); printf("%d\n",solve()); ; }
——————分割线——————
这道题我Debug了2天共计5h,最后偶然间查明了死因居然是——
#ifdef WRONG_SPLAY_CODE void Splay::splay() { reverse(); while(!isRoot()) { ); ]) st|=; ; if(!parent->isRoot()) { ]) st|=; ; } switch(st) { : rotate(); break; : rotate(); break; : parent->rotate(); ); break; : rotate(); rotate(); break; : rotate(); rotate(); break; :parent->rotate(); ); break; } } } #endif
I FELL COLLAPSED BECAUSE OF THIS
不过在Debug期间,参考了不少其他神犇的AC代码,也学到了各种姿势,算是因祸得福吧……