★★★☆   输入文件：magicalforest.in   输出文件：magicalforest.out   简单对比

　　　　　　　　　　　　　　　　　　　　　　时间限制：2 s   内存限制：512 MB

题解：

　　每条边有两种权值，所以想到先对一种权值A进行排序，然后一条一条地加边，如果有环，就特殊判断，在这题中就是删掉该环上B值最大的边。直到1和N之间连通，就更新答案。

　　由于牵涉到连边和删边的操作，所以可以用动态树来维护。但是动态树里都是点权，题目中的边权很难处理，所以我们可以在两点之间的边上多加一个点，中间的点的权值就是边权，两端点的权值就是0，三个点成一条边，为了方便起见，中间的点的编号设为N+i,i为当前边的编号，以此来增减边。

　　还有一个问题，就是如何找到某环上的最大B值。对于当前要连接的两点(u,v)，如果连了，就会形成环，现在rever(u),再access(v)，u和v之间的路径就存在一棵splay里了，可以给splay定义一个mx[]值，mx[i]=k的意思是在以i为根的splay里，点权最大的点是k点，再搞一个val[]数组记录下点的B值。每次splay的时候更新一下，还有在cut，link的时候也要更新。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std; 10 const int maxn=50010*4; 11 inline int read(){ 12 int x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 int N,M,ANS=1e9; 18 struct node{ 19 int x,y,A,B; 20 }e[maxn]; 21 int cmp(const node & a,const node & b){ 22 if(a.A
             
              val[mx[x]]) mx[x]=mx[l]; 35 if(val[mx[r]]>val[mx[x]]) mx[x]=mx[r]; 36 } 37 void pushdown(int x){ 38 int l=c[x][0],r=c[x][1]; 39 if(rev[x]==true){ 40 rev[x]^=1; rev[l]^=1; rev[r]^=1; 41 swap(c[x][0],c[x][1]); 42 } 43 } 44 void rotate(int x){ 45 int y=fa[x],z=fa[y],l,r; 46 if(x==c[y][0]) l=0;else l=1;r=l^1; 47 if(!isroot(y)){ 48 if(y==c[z][0]) c[z][0]=x; 49 else c[z][1]=x; 50 } 51 fa[x]=z; fa[y]=x; fa[c[x][r]]=y; 52 c[y][l]=c[x][r]; c[x][r]=y; 53 pushup(y); pushup(x); 54 } 55 56 void splay(int x){ 57 int top=0; st[++top]=x; 58 for(int i=x;!isroot(i);i=fa[i]){ 59 st[++top]=fa[i]; 60 } 61 for(int i=top;i;i--) pushdown(st[i]); 62 while(!isroot(x)){ 63 int y=fa[x],z=fa[y]; 64 if(!isroot(y)){ 65 if((x==c[y][0]&&y==c[z][0])||(x==c[y][1]&&y==c[z][1])){ 66 rotate(y); rotate(x); 67 } 68 else rotate(x),rotate(x); 69 } 70 else rotate(x); 71 } 72 } 73 void access(int x){ 74 int t=0; 75 while(x){ 76 splay(x); 77 c[x][1]=t; 78 pushup(x); 79 t=x; x=fa[x]; 80 } 81 } 82 void rever(int x){ 83 access(x); splay(x); rev[x]^=1; 84 } 85 void cut(int x,int y){ 86 rever(x); access(y); splay(y); 87 c[y][0]=fa[x]=0; pushup(y); 88 } 89 void link(int x,int y){ 90 rever(x); fa[x]=y; splay(x); 91 } 92 int find(int x){ 93 access(x); splay(x); 94 while(c[x][0]) x=c[x][0]; 95 return x; 96 } 97 int query(int x,int y){ 98 rever(x); access(y); splay(y); 99 return mx[y];100 }101 int main(){102 freopen("magicalforest.in","r",stdin);103 freopen("magicalforest.out","w",stdout); 104 N=read(); M=read();105 for(int i=1;i<=M;i++){106 e[i].x=read(); e[i].y=read();107 e[i].A=read(); e[i].B=read();108 }109 sort(e+1,e+M+1,cmp);110 int tot=0;111 for(int i=1;i<=M;i++){112 int u=e[i].x,v=e[i].y,a=e[i].A,b=e[i].B;113 if(find(u)==find(v)){ //在同一个连通块中 114 int t=query(u,v);//删去一个环里B值最大的边 115 if(val[t]>e[i].B){116 cut(t,e[t-N].x);117 cut(t,e[t-N].y);118 }119 else{120 if(find(1)==find(N))121 ANS=min(ANS,e[i].A+val[query(1,N)]);122 continue;123 }124 }125 val[N+i]=e[i].B; mx[N+i]=N+i;//u,v之间添加一个节点，点权即为边权 126 link(u,N+i); link(v,N+i);127 if(find(1)==find(N)) ANS=min(ANS,e[i].A+val[query(1,N)]);//更新 128 }129 if(ANS==1e9) puts("-1");130 else printf("%d\n",ANS);131 return 0;132 }