洛谷P1111 修复公路    

并查集   图论  最小生成树

题意 不断往图中加边，加边有时间，求这张图什么时候互相连通

开始的时候我太naive，想到的是 传递闭包 +bitset 压位优化

这样 nm 100000000 感觉可以，就是常数太大

然后发现 可以用最小生成树来做

最小生成树中所有点都互相连通，以时间为权值，最早的时间就是生成树

中最大的那条边

不过我不知道为什么一定要交换一下，那位大神知道帮我解释一下。。。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ; 10 11 const int maxn = 1011,maxm = 100011 ; 12 struct node{13 int from,to,val ; 14 }e[2*maxm]; 15 int n,m,dx,dy,x,y,v ; 16 int fa[maxn],size[maxn] ; 17 18 inline int find(int x)19 {20 if(fa[x]==x) return x ; 21 fa[x] = find(fa[x]) ; 22 return fa[x] ; 23 }24 25 bool cmp(node a,node b) 26 {27 return a.val < b.val ; 28 }29 30 int main() 31 {32 scanf("%d%d",&n,&m) ; 33 for(int i=1;i<=m;i++) 34 {35 scanf("%d%d%d",&x,&y,&v) ; 36 e[ i ].from = x ; 37 e[ i ].to = y ; 38 e[ i ].val = v ;39 }40 for(int i=1;i<=n;i++) fa[ i ] = i,size[ i ] = 1 ; 41 sort(e+1,e+m+1,cmp) ; 42 for(int i=1;i<=m;i++) 43 {44 dx = find(e[ i ].from) ; 45 dy = find(e[ i ].to) ; 46 if(dx==dy) continue ; // 这里貌似一定得交换 47 if(dx > dy) swap(dx,dy) ; 48 fa[dy] = dx ; 49 size[dx] = size[dx]+size[dy] ; 50 if(size[dx]==n) 51 {52 printf("%d\n",e[ i ].val) ; 53 return 0 ; 54 }55 }56 printf("-1\n") ; 57 return 0 ; 58 }