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; }
}
哔哩哔哩公司福利 732人发布
