最小生成树(无向图)

prim: 朴素版 $O(n^2)$；堆优化版(适合稠密图) $O(m\log n)$，用的少；

kruskal: $O(m\log m)$

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int g[N][N], d[N], st[N];
int n, m;
int prim(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 1; i < n; i ++){
        int x = -1;
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (x == -1 || d[j] < d[x])) x = j;  
        } 
        st[x] = 1;
        for(int y = 1; y <= n; y ++){
            if(!st[y]) d[y] = min(d[y], g[x][y]);
		}
    }
    int res = 0;
    for(int i = 1; i <= n; i ++) res += d[i];
    return res;
}
int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    for(int i = 1; i <= n; i ++) g[i][i] = 0;
    for(int i = 0; i < m; i ++){
        int a, b, c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    cout << prim();
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int p[N];
int n, m;
struct Edge{
    int a, b, w;
    bool operator<(const Edge &edge)const{
        return w < edge.w;
    }
}edges[N];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i ++){
        int a, b, w; cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    sort(edges, edges + m);
    for(int i = 1; i <= n; i ++) p[i] = i;
    int res = 0, cnt = 0; // cnt: 加入的边数
    for(int i = 0; i < m; i ++){
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);
        if(a != b){
            p[a] = b;
            res += w;
            cnt ++;
        }
    }
    if(cnt < n - 1) cout << "impossible";
    eles cout << res;
}

二分图

染色法 $O(m+n)$；匈牙利算法最坏 $O(mn)$，一般远远小于这个；

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];

bool dfs(int u, int c){
    color[u] = c;
    for(int i = h[u]; i != -1; i = ne[i]){
        int y = e[i];
        if(!color[y]){
            if(!dfs(y, 3 - c)) return false;
        }
        else if(color[y] == 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) cout << "Yes";
    else cout << "No";
}
// 作业：257

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N], st[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

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

int main(){
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int a, b; cin >> a >> b;
        add(a, b);
    }
    int res = 0;
    for(int i = 1; i <= n1; i ++){
        memset(st, 0, sizeof st);
        if(dfs(i)) res ++;
    }s
    cout << res;
}
// 作业：372

Q.E.D.