题意：给定一张无向图，图中每个边都有a,b两种边权，求一条从S到T的路径，使得路径中（a的最大值+b的最大值）最小

法一：我们先将边按a排序，每次加入一条边，然后将加入的边的两端入队，跑一边SPFA求从1到达每个节点路径上的最长的一条边的长度。这样需要跑M边SPFA，然而有一个优化——我们可以直接将所有a相同的边一次性全部入队然后跑一遍SPFA，每跑完一遍SPFA用a+d[N]来更新答案，这样的复杂度理论上是TLE的然而并没有- -，而且实际上这玩意跑起来比LCT还要快……（毕竟LCT天生自带大常数而且数据比较水）

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;const int MAXN=50000+2;const int MAXM=100000+2;struct HASH{ int u,w; HASH *next; HASH(){} HASH(int _u,int _w,HASH *_next):u(_u),w(_w),next(_next){}}*table[MAXN],mem[2*MAXM];struct EDGE{ int u,v,a,b;}e[MAXM];int N,M,d[MAXN],ans=INT_MAX>>1,cnt;bool flag[MAXN];queue
             
               q;bool cmp(EDGE x,EDGE y){ return x.a
              
               next) if(d[p->u]>max(d[x],p->w)){ d[p->u]=max(d[x],p->w); if(!flag[p->u]) flag[p->u]=1,q.push(p->u); } flag[x]=0; }}int main(){ cin >> N >> M; for(int i=1,u,v,a,b;i<=M;i++) cin >> e[i].u >> e[i].v >> e[i].a >> e[i].b; sort(e+1,e+M+1,cmp); for(int i=1;i<=N;i++) d[i]=INT_MAX>>1; d[1]=0; for(int i=1;i<=M;i++){ Insert(e[i].u,e[i].v,e[i].b); while(i
               
                =INT_MAX>>1) cout << -1 << endl; else cout << ans << endl; return 0;}
               
              
             
            
           
          
         
        
       
      

法二：

边按a排序后按顺序加边，用LCT动态维护最小生成树。

维护最小生成树：并查集记录哪些点已经相连，每加入一条边时，如果该边所连的两个点(u,v)已经相连，那么查找(u,v)上的最大边权，如果该边权大于当前加入的边权，则将最大边权的边删除，同时将当前加入的边加入，否则不做处理。然后每次用a+1到N路径上的最大边权来更新答案。

有一个细节就是每条边单独建点，这样可以大大优化编程复杂度。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int MAXN=100000+2;const int MAXM=200000+2;typedef struct NODE{ int m,r; NODE *child[2],*f; bool rev; NODE(){} NODE(int _m,NODE *_f):m(_m),r(_m),f(_f),rev(0){}} *TREE;TREE root,Null,mark[MAXN],mark_e[MAXM];struct EDGE{ int u,v,a,b;}e[MAXM];int N,M,ans=INT_MAX;bool cmp(EDGE x,EDGE y){ return x.a
            
             child[0]=x->child[1]=Null; return x;}void Pushup(TREE &x){ x->r=x->m; if(e[x->child[0]->r].b>e[x->r].b) x->r=x->child[0]->r; if(e[x->child[1]->r].b>e[x->r].b) x->r=x->child[1]->r;}void Pushdown(TREE &x){ if(x->f->child[0]==x || x->f->child[1]==x) Pushdown(x->f); if(x->rev){ swap(x->child[0],x->child[1]); x->child[0]->rev^=1,x->child[1]->rev^=1,x->rev=0; }}void Rotate(TREE &x,bool t){ TREE y=x->f; y->child[!t]=x->child[t],x->child[t]->f=y,x->f=y->f; if(y->f->child[0]==y) y->f->child[0]=x; if(y->f->child[1]==y) y->f->child[1]=x; y->f=x,x->child[t]=y; Pushup(y);}void Splay(TREE &x){ Pushdown(x); TREE y=x->f; while(y->child[0]==x || y->child[1]==x){ if(y->child[0]==x){ if(y->f->child[0]==y) Rotate(y,1); Rotate(x,1); } else{ if(y->f->child[1]==y) Rotate(y,0); Rotate(x,0); } y=x->f; } Pushup(x);}void Access(TREE &x){ TREE y=Null,z=x; while(z!=Null){ Splay(z),z->child[1]=y; Pushup(z); y=z,z=z->f; }}void Move(TREE &x){ Access(x),Splay(x); x->rev^=1,Pushdown(x);}void Link(TREE &x,TREE &y){ Move(x),x->f=y;}void Cut(TREE &x,TREE &y){ Move(x),Access(y),Splay(y); y->child[0]=x->f=Null,Pushup(y);}TREE Find(TREE &x){ TREE y=x; while(y->f!=Null) y=y->f; return y;}int Query(TREE &x,TREE &y){ Move(x),Access(y),Splay(y); return y->r;}int main(){ memset(e,0,sizeof(e)); cin >> N >> M; for(int i=1;i<=M;i++) cin >> e[i].u >> e[i].v >> e[i].a >> e[i].b; Null=NewNode(0,0); sort(e+1,e+M+1,cmp); for(int i=1;i<=M;i++) mark[i]=NewNode(0,Null); for(int i=1,t;i<=M;i++){ if(e[i].u==e[i].v) continue; mark_e[i]=NewNode(i,Null); if(Find(mark[e[i].u])==Find(mark[e[i].v])){ t=Query(mark[e[i].u],mark[e[i].v]); if(e[i].b>=e[t].b) continue; Cut(mark[e[t].u],mark_e[t]),Cut(mark_e[t],mark[e[t].v]); } Link(mark[e[i].u],mark_e[i]),Link(mark_e[i],mark[e[i].v]); if(Find(mark[1])==Find(mark[N])) ans=min(ans,e[i].a+e[Query(mark[1],mark[N])].b); } if(ans==INT_MAX) cout << -1 << endl; else cout << ans << endl; return 0;}