11.19算法学习打卡

约 88 个字 54 行代码预计阅读时间 1 分钟

算法打卡一定要打卡
考完期中，开运动会放了几天假，这几天也没学，~~一直在玩粥和鸣潮~~）
上学期数据结构与算法没有好好学，自己逃避的东西还是会来找上你。
消耗了多于两倍的时间，最后还记不住拿不出手，
Kruskal算法

C++
#include<bits/stdc++.h>
using namespace std;
using LL = long long;

vector<int>father;
vector<int>resultu;
vector<int>resultv;
vector<int>resultw;
struct edge {//定义边结构体
    int u, v;
    LL weight;
};
bool cmp(edge a, edge b) {
    return a.weight > b.weight;
}
int findfather(int x) {  //寻找父节点
    while (father[x] != x) {
        x = father[x];
    }
    return x;
}
void kruskal(int n,vector<edge> Edge) {
    father.resize(n);
    sort(Edge.begin(), Edge.end(), cmp);
    for (int i = 0; i < n; i++) {
        father[i] = i;  //初始化并查集
    }
    for (int i = 0; i < Edge.size() && resultw.size() < n - 1 ; i++) {
        int u = Edge[i].u;
        int v = Edge[i].v;
        if (findfather(u) != findfather(v)) {
            resultu.push_back(u);
            resultv.push_back(v);
            resultw.push_back(Edge[i].weight);
            father[findfather(v)] = father[findfather(u)];
        }
    }
    for (int i = 0; i < resultw.size(); i++) {
        cout << resultu[i] << " " << resultv[i] << " " << resultw[i] << endl;
    }//输出最小生成树
}

int main() {
    int n;
    int m;
    int c;
    cin>>n>>m>>c;
    vector<edge> edges(m);
    for(int i=0;i<m;i++) {
        cin>>edges[i].u>>edges[i].v>>edges[i].weight;
    }
    kruskal(n,edges);
    return 0;
}

11.19算法学习打卡

评论