最小生成树

• 无向图中把2图中的所有边权节点连接起来。要求边长之和最小叫做最小生成树

• 一个图有不同的生成树 不同的生成树有不同的权值和

类似dijkstra

prim算法

#include <iostream>
#include <cstring>
using namespace std;
​
const int N = 1e6+10;
​
int h[N],e[N],ne[N],nv[N],idx = 0;
​
void add(int a,int b,int c){
    e[idx] = b;
    nv[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}
​
int pri[N],dist[N];
bool st[N];
    
    int n,m;
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res = 0;
    dist[1] = 0; // 从1开始
    for(int i = 1;i <= n;i ++){ //n个点
        int t = -1;
        for(int j = 1;j<=n;j++){
            if(!st[j]&&(t == -1 || dist[t] > dist[j]))t = j;
        }
        
        if(dist[t] == 0x3f3f3f3f){
            return -1; // 没有找到
        }
        res += dist[t]; // 加上
        st[t] = 1;
        
        for(int j = h[t];~j;j = ne[j]){
            int d = e[j];
            int v = nv[j];
            if(dist[d]>v&&!st[d]){
                dist[d] = v;
                pri[d] = t;
            }
        }
        
    }
// 找到值
    return res;
    
}
​
​
int main(){
​
    memset(h,-1,sizeof h);
    cin >> n >> m ;
    
    for(int i = 1;i <= m;i ++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    
    int res = prim();
    
    if(res == -1){
        cout << "orz" << endl;
    }else{
        cout << res << endl;
    }
    
    
    return 0;
}
​

k r u s k a l 算法

结构体存所有的边，两端链接顶点

对所有边进行排序

选出最短不构成环的边，加入最小生成树集合，知道所有点加入

形成环不采取选择

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
​
​
​
const int N = 1e5;
​
struct Edge{
​
    int a,b,w;
    bool operator <(const Edge &W){ //重写小于号
        return w<W.w;   
    }
​
}edge[N];
​
int m,n;
​
int p[N]; // 并查集
​
​
int find(int x){
    if(p[x] == x)return p[x];
    return find(p[x]);
}
​
int kruskal(){
​
    sort(edge,edge+m);
​
    for(int i = 1;i<=n;i++)p[i] = i; //初始化并查集
​
    int res = 0,cnt = 0; //// res用于记录最小生成树的权值和，cnt用于记录加入的边数
​
    for(int i=0;i < m;i++){
        int a = edge[i].a;
        int b = edge[i].b;
        int w = edge[i].w;
​
        a = find(a),b = find(b); // 找到a和b的根节点
        if(a!=b){                // 如果a和b不在同一个连通分量中
            p[a] = b;            // 合并连通分量，将a的根节点指向b的根节点
            res += w; 
            cnt ++;       //边数++
        }
    }
​
    if(cnt < n-1)return -1;
​
    return res;
​
}
​
​
int main(){
​
      cin >> n >> m ;
    
    
    for(int i = 0;i < m;i ++){
        int a,b,c;
        cin >> a>>b>>c;
        edge[i].a = a;
        edge[i].b = b;
        edge[i].w = c;
    }
    
    
    int res = kruskal();
    
    if(res == -1){
        cout << "orz" << endl;
    }else{
        cout << res << endl;
    }
​
    return 0;
}

二分图

• 两个顶点集 每条边两个顶点分别位于顶点集中，每个顶点集都没有与边直接相连

染色法

• 判断一个图是不是二分图

• 对任意没染色的点染色

• 判断相邻点中没染色，将相邻点染上不同的颜色

• 如果已经染色，且相邻顶点相同则说明不是二分图

​
const int N  = 1000010;
//  邻接表
​
int color[N];
​
​
bool dfs(int u,int c){
    color[u] = c; // 染色该点
    for(int i = h[u];~i;i = ne[i]){
        int j = e[i];
        if(!color[j]){
            if(!dfs(j,3-c)) return false;
        }else if(color[j]&&color[j]!=3-c){
            
            //处理冲突
            return false;
        }
    }
    
    return true;
}
​
int main(){
for(int i=1;i<=n;i++){ //遍历点
    if(!color[i]){
        if(!dfs(i,1)){
            cout << "NO" <<endl;
            return 0;
        }
    }
}
cout <<"Yes" << endl;
return 0;
}

匈牙利算法

#include <iostream>
#include <cstring> // 包含 memset 函数
using namespace std;
​
const int N = 1e5 + 10;
​
int h[N], e[N], ne[N], idx;
int st[N], match[N]; // st 数组用于标记节点是否已经被访问过，match 数组用于记录匹配信息
int 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; i = ne[i]) {
        int b = e[i];
        if (!st[b]) { // 如果节点未被访问过
            st[b] = 1; // 标记节点为已访问
            if (match[b] == 0 || find(match[b])) { // 如果节点未匹配或者与当前节点匹配的节点可以找到增广路径
                match[b] = x; // 更新匹配信息
                return true; // 找到增广路径
            }
        }
    }
    return false; // 未找到增广路径
}
​
int main() {
    int res = 0; // 存储最大匹配数量
    for (int i = 1; i <= n; i++) {
        memset(st, 0, sizeof st); // 清空标记数组
        if (find(i)) res++; // 寻找增广路径，并更新最大匹配数量
    }
​
    cout << res << endl; // 输出最大匹配数量
    
    return 0;
}