1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define N 450005  6 #define M 300005  7 #define lc(x) ch[x][0]  8 #define rc(x) ch[x][1]  9 #define inf 0x3f3f3f3f 10 using namespace std; 11 int f[N]; 12 int n,m,cnt; 13 struct node 14 { 15     int x,y,a1,a2; 16     friend bool operator < (node aa,node bb) 17     { 18         return aa.a1
         
          bian[i].a2)136             {137                 int t=find(bian[i].y,mx[bian[i].y]);138                 cut(t,bian[t-n].x);cut(t,bian[t-n].y);139                 link(bian[i].x,i+n);link(bian[i].y,i+n);140             }141         }142         if(fnd(1)==fnd(n))143         {144             split(1,n);145 //          dfs(2);146             ans=min(ans,bian[i].a1+mx[n]);147 //          cout<
          
           <<' '<
           
            <
           
          
         
        
       
      
     

动态最小生成树