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; } }