你不觉得这个博客太水了么？
对于我这种没前途的人，也只能靠刷水过日子了……
普通的最小生成树。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,f[305];
struct Node{
int a,b,v;
}a[90005];
int cmp(const void *a,const void *b){
return (*(Node *)a).v>(*(Node *)b).v?1:-1;
}
int Find(int i){
return i==f[i]?i:f[i]=Find(f[i]);
}
void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}
int main(){
freopen("1083.in","r",stdin);
freopen("1083.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&a[i].a,&a[i].b,&a[i].v);
}
qsort(a,m,sizeof(Node),cmp);
int fff=0;
for(int i=1;i<=m;i++){
if(Find(a[i].a)!=Find(a[i].b)){fff++;Union(Find(a[i].a),Find(a[i].b));if(fff==n-1){printf("%d %d\n",n-1,a[i].v);}}
}
return 0;
}
评论 (0)
