prim

#include <bits/stdc++.h>

using namespace std;

const int N = 510 ,INF = 0x3f3f3f3f; 

int n , m ; 
int dist[N] , g[N][N];
bool st[N];

int prim(){
    memset(dist , 0x3f , sizeof dist);
    int res = 0;
    for(int i = 0 ; i < n ; i ++ ){
        int t = -1 ; 
        for(int j = 1 ; j <= n ; j ++ )
            if(!st[j] && (t == -1 || dist[t] > dist[j]))t = j;
        if(i && dist[t] == INF)return INF;
        if(i) res += dist[t];
        st[t] = true;
        for(int j = 1 ; j <= n ; j ++ )
            dist[j] = min(dist[j] , g[t][j]);
    }
    return res;
}

int main(){
    cin >> n >> m ;
    memset(g , 0x3f , sizeof g);
    while(m --){
        int a , b , c ;
        cin >> a >> b >> c ; 
        g[a][b] = g[b][a] = min(g[a][b] , c);
    }
    int t = prim();
    if(t == 0x3f3f3f3f)puts("impossible");
    else cout << t << endl;
    return 0 ; 
}

kruskal

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10 , M = 2e5+10;

struct Edge{
    int a , b , w ; 
    bool operator < (const Edge &W ) const{
        return w < W.w ; 
    }
}edge[M];

int p[N] , n , m ;
int ans , cnt ; 

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

int kruskal(){
    sort(edge , edge + m );
    for(int i = 1 ; i <= n ; i ++ ) p[i] = i ;
    for(int i = 0 ; i < m ; i ++ ){
        int a = edge[i].a , b = edge[i].b , w = edge[i].w ;
        a = find(a) , b = find(b);
        if(a != b){
            p[a] = b ;
            ans += w ;
            cnt ++ ;
        }
    }
    if(cnt < n - 1)return -1 ;
    else return ans ; 
}

int main()
{
    cin >> n >> m ;
    for(int i = 0 ; i < m ; i ++ ){
        int a , b , w ;
        cin >> a >> b >> w ;
        edge[i] = { a , b , w }; 
    }
    int t = kruskal();
    if(t == -1) puts("impossible");
    else cout << ans << endl;
    return 0 ; 
}

染色法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10 , M = 2e5+10;

int h[N] , e[M] , ne[M] , idx ; 
int n , m ;
int color[N];

void add(int a , int b ){
    e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}

bool dfs(int u , int c ){
    color[u] = c ;
    for(int i = h[u] ; i != -1 ; i = ne[i]){
        int j =e[i];
        if(!color[j]){
            if(!dfs(j , 3 - c))return false;
        }else if(color[j] == c)return false;
    }
    return true;
}

int main()
{
    cin >> n >> m ;
    memset(h , -1 , sizeof h);
    for(int i = 0 ; i < m ; i ++ ){
        int a , b ; cin >> a >> b ;
        add(a , b ); add(b , a);
    }
    bool flag = true;
    for(int i = 1 ; i <= n ; i ++ ){
        if(!color[i]){
            if(!dfs(i , 1)){
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0 ; 
}

匈牙利算法

#include <bits/stdc++.h>

using namespace std;

const int N = 510 , M = 1e5+10;

int n1 , n2 , m ;
int h[N] , e[M] , ne[M] , idx ;
int match[N];
bool st[N];

void add(int a , int b ){
    e[idx] = b ; 
    ne[idx] = h[a];
    h[a] = idx ++ ;
}

bool find(int x){
    for(int i = h[x] ; i != -1 ; i = ne[i]){
        int j =e[i];
        if(!st[j]){
            st[j] = true;
            if(match[j] == 0 || find(match[j])){
                match[j] = x ;return true;
            }
        }
    }
    return false;
}

int main(){
    cin >> n1 >> n2 >> m ;
    memset(h , -1 , sizeof h);
    while(m -- ){
        int a , b ;
        cin >> a >> b ; 
        add(a , b );
    }
    int ans = 0 ;
    for(int i = 1; i <= n1 ; i ++ ){
        memset(st , false , sizeof st);
        if(find(i)) ans ++ ; 
    }
    cout << ans << endl ;
    return 0 ; 
}