最小生成树，两种方法，我之前的分享中有写， 最小生成树
或者y总的代码模板 最小生成树算法模板

先看hdu1162 hdu1162
题目大意
每组测试样例第一行给你一个n，再给你n行，每行一个点的坐标，，求得该组所有点连接的最小距离
Sample Input
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output
3.41
注意这道题是到文件尾结束输入
代码如下

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std ;

struct edge{          //存边
    int a,b ;
    double v ;
    bool operator < (edge z){
        return v < z.v ; 
    }
};
typedef pair<double,double> pdd ;
const int N = 110 ;
int p[N] ;             //并查集
vector<edge> v ;         //存边的信息
pdd point[N] ;         //存n个点坐标
int n;

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;
}
void marge(int a,int b){      //经典并查集
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}
double dist(int i,int j){     //返回两个点之间的距离
    return sqrt((point[i].first - point[j].first) * (point[i].first - point[j].first) + (point[i].second - point[j].second) * (point[i].second - point[j].second)) ;
}
void kruskal(){      //kruskal算法
    for(int i = 0 ; i <= n ; i++){        //重置并查集
        p[i] = i ;
    }

    sort(v.begin(),v.end()) ;          //对边的权值排序

    double res = 0 ;
    for(size_t i = 0 ; i < v.size() ; i++){
        int a = v[i].a , b = v[i].b ;
        if(find(a) != find(b)){
            marge(a,b) ;
            res += v[i].v ;              //记录res
        }
    }
    printf("%.2f\n",res) ;
}

int main(){
    while(cin >> n){        //读入n，文件尾结束
        for(int i = 1 ; i <= n ; i++){        //读入点
            cin >> point[i].first >> point[i].second ;
        }
        v.clear() ;                         //清空边，
        for(int i =  1 ; i <= n ; i++){
            for(int j = i+ 1 ; j <= n ; j++){
                v.push_back({i,j,dist(i,j)}) ;        //根据n个点的坐标求得边，存到vector中
            }
        }

        kruskal() ;
    }

    return 0 ;
}

最大生成树,使用kruskal算法时，把比较符号的重载为想要的排序即可

Bad Cowtractors Bad Cowtractors
题目大意
第一行为n和m，n代表谷仓编号，m代表路的方案数，接下来m行，每行a，b，c，代表从a到b花费c
求最大连通成本
Sample Input
5 8
1 2 3
1 3 7
2 3 10
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17
Sample Output
42

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std ;

struct edge{
    int a,b,v ;
    bool operator < (const struct edge z) const{         //注意将排序重载反一下即可
                                                        //也可以在排序完再逆序一下
        return v > z.v ;
    }
};
const int N = 1100 ;
vector<edge> v ;
int p[N] ;
int n ,m ;

int find(int x){
    if(p[x] != x) p[x] = find(p[x]) ;
    return p[x] ;
}

void marge(int a,int b){       //经典并查集
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}

void kruskal(){        //经典kruskal算法
    for(int i = 0 ; i <= n ; i++){
        p[i] = i ;
    }

    sort(v.begin(),v.end()) ;

    int res = 0  ;
    int cnt = 0 ;
    for(size_t i = 0 ; i < v.size() ; i ++){
        int a = v[i].a , b = v[i].b ;
        if(find(a) != find(b)){
            marge(a,b) ;
            cnt ++ ;
            res += v[i].v ;
        }
    }
    if( cnt != n - 1){
        cout << -1<<endl ;
        return ;
    }
    cout << res <<endl ;
}

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;

    cin >>n >> m ;

    for(int i = 0 ; i < m ; i++){
        int a,b,c;
        cin >> a >>b >> c ;
        v.push_back({a,b,c}) ;      //经典输入边
    }

    kruskal() ;

    return 0 ;
}

hdu5627 Clarke and MST Clarke and MST

这道题还是最大生成树，这个最大生成树是每一个权值进行与&操作
就普通的写最大生成树，将每个边的权值进行与操作即可

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std ;

struct edge{
    int a,b,c ;
    bool operator < (const struct edge z)const{
        return c > z.c ;
    }
};

const int N = 3e5 + 100 ;
int p[N] ;
vector<edge> v ;
int n,m ;

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;                          //经典并查集
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}

void kruskal(){
    for(int i = 0 ; i <= n ;i++){
        p[i] = i ;
    }

    sort(v.begin(),v.end()) ;

    int res = 1 ;                       //初始化为1
    int cnt = 0 ;
    for(size_t i = 0 ; i < v.size() ; i++){
        int a = v[i].a , b = v[i].b ;
        if(find(a) != find(b)){
            marge(a,b) ;
            res &= v[i].c ;              //每个边的权值进行与&操作
            cnt ++ ;
        }
    }
    if(cnt != n - 1){
        cout << 0 <<endl ;
        return ;
    }
    cout << res <<endl ;
}

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0) ;                 //不加速的话过不去，会tle
    int t ;
    cin >> t ;

    while(t--){
        cin >> n >> m ;
        v.clear() ;
        for(int i = 0 ; i < m ; i++){
            int a,b,c;
            cin >>a >>b>> c;
            v.push_back({a,b,c}) ;
        }

        kruskal() ;
    }
    return 0 ;
}