请选择 进入手机版 | 继续访问电脑版

最小生成树与二分图

[复制链接]
孤单 发表于 2021-1-2 19:44:36 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
最小生成树与二分图




最小生成树

Prim算法

  https://www.acwing.com/problem/content/860/

  算法思想
维护一个聚集,每次找到一条集会合点可以到达的最小的边,然后把这条边的终点记录在集会合,继承重复迭代,直到所有的点都选择完毕。
时间复杂度:因为是两层循环,所以说时间复杂度照旧O(n2)。

  算法流程

  源代码
[code]#include #include #include using namespace std;const int N = 510, M = 1e5 + 10, INF = 0x3f3f3f3f;int dist[N], g[N][N];bool vis[N];int n,m;int u,v,w;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 >> m;    memset(g, 0x3f, sizeof g);    for(int i = 0; i < m; i++) {        cin >> u >> v >> w;        g[v] = g[v] = min(w, g[v]);  // 重边 & 无向图    }        int t = prim();        if(t == -1) puts("impossible");    else cout > m;    for(int i = 0; i < m; i++) {        int u,v,w;        cin >> u >> v >> w;        e = {u,v,w};    }        int t = kruskal();        if(t == -1) puts("impossible");    else cout  n >> m;    memset(h, -1, sizeof h);    for(int i = 0; i < m; i++) {        int u,v;        cin >> u >> v;        add(u,v), add(v,u);    }        bool flag = true;    for(int i = 1; i > m;    memset(h, -1, sizeof h);    for(int i = 0; i < m; i++) {        int u,v;        cin >> u >> v;        add(u,v);    }        int res = 0;    for(int i = 1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )