最小生成树和二分图

本文主要是介绍最小生成树和二分图，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Prim

与dijistra比较像，分为朴素版和堆优化版。
朴素版Prim，时间复杂度O(n^2)，一般用于稠密图。
算法流程：初始化距离矩阵为0x3f3f3f3f.
循环n次，找到距离集合最短的点t，用t更新其他点到集合的距离。
注意：与dijistra不同的在与距离的更新方式。
Prim最小生成树

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 510;
int g[maxn][maxn],n,m;
int dis[maxn];
bool st[maxn];
int prim(){
    int ans=0;
    memset(dis,0x3f,sizeof dis);
    for(int i=0;i<n;i++){
        int t = -1;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dis[j]<dis[t]))
                t = j;
        }
        if(i && dis[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i) ans += dis[t];
        for(int i=1;i<=n;i++) dis[i] = min(dis[i],g[t][i]);
        st[t] = true;
    }
    return ans;
}
int main(){
    cin>>n>>m;
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d%d%d",&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;
    return 0;
}

堆优化版Prim，时间复杂度O(m*logn)，一般不常用。

Kruskal

时间复杂度O(m*logm)，一般用于稀疏图。
算法流程：
1.将所有边按照权重大小，从小到大排序。
2.枚举每条边a,b。如果a,b不连通，则将边加入集合。
Kruskal

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2e5 + 10;
const int N=1e5 + 10;
int n,m,p[N];
struct Edge{
    int a,b,c;
}edges[maxn];
bool cmp(Edge a,Edge b){
    return a.c < b.c;
}
int find(int x){
    if(p[x] != x) return p[x] = find(p[x]);
}
int kluskal(){
    sort(edges + 1,edges + 1 + m,cmp);
    int ans=0,cnt=0;
    for(int i=1;i<=m;i++){
        int a = edges[i].a,b = edges[i].b,c = edges[i].c;
        a = find(a),b=find(b);
        if(a != b){
            p[a] = b;
            ans += c;
            cnt++;
        }
    }
    if(cnt < n-1) return -1;
    else return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) p[i] = i;
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges[i]={a,b,c};
    }
    int t = kluskal();
    if(t==-1) puts("impossible");
    else cout<<t<<endl;
    return 0;
}

判断二分图

O(m+n)

匈牙利算法

这篇关于最小生成树和二分图的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！