k什么。。。。 MST算法

啊,这个名字好难打

这也是个暴力,就是对权值排序,然后检查构成环就不拿
。。。。。。。。。
我刚开始打的程序和模板一模一样。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int n,m;
long long maxl=9999999;
int p[10005][10005];
int fa[10005];
int cost[10005];
bool vis[10005];
int d[10005],num=0;
struct node{     int from,to,cost;
}point[10005];

bool cmp(node x,node y){     return x.cost<y.cost;
}

int found(int x){     if(fa[x]==x)return x;         fa[x]=found(fa[x]);         return fa[x];
}

int main(){     cin>>n>>m;     for(int i=1;i<=n;i++){         for(int j=1;j<=n;j++){             p[i][j]=maxl;         }         vis[i]=         fa[i]=i;     }     for(int i=1;i<=m;i++){         int u,v,w;         cin>>u>>v>>w;         p[u][v]=min(p[u][v],w);         p[v][u]=min(p[v][u],w);         point[i].from=u;         point[i].from=v;         point[i].cost=w;     }     sort(point+1,point+1+m,cmp);     for(int i=1;i<=m;i++){         if(found(point[i].from)!=found(point[i].to)){             fa[point[i].from]=point[i].to;             d[num]=point[i].cost;             num++;             if(num==n-1)break;         }     }     for(int i=0;i<num;i++){         cout<<d[i]<<endl;     }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 11:15
点赞 评论 收藏
分享
Yki_:你要算时间成本呀,研究生两三年,博士三四年,加起来就五六年了,如果你本科去腾讯干五年,多领五年的年薪,加上公司内涨薪,可能到时候十五年总薪资也跟博士差不多
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务