代码37分,最后一个特判orz点能过。WA的点全是因为错误输出orz。 初步判断是被Xi==Yi的情况卡掉了,求神犇救命
#include<bits/stdc++.h>
using namespace std;
const int N=20005;
int n,m,u,v,father[N],ans,tag;
struct edge{
int start,to;long long val;
}bian[2000005];
bool cmp(edge a,edge b){
return a.val<b.val;
}
int find(int x){
if(x==father[x])return x;
return father[x]=find(father[x]);
}
void bing(int x,int y){
x=find(x),y=find(y);
father[x]=y;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)father[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&bian[i].start,&bian[i].to,&bian[i].val);
}
sort(bian+1,bian+m+1,cmp);//快排边长
for(int i=1;i<=n;i++){//kruskal
u=find(bian[i].start),v=find(bian[i].to);
if(u==v)continue;
father[u]=v;
tag++;//边的数量
ans+=bian[i].val;
if(tag==n-1)break;//树已成型
}
for(int i=1;i<n;i++){
//cout<<find(i)<<endl;//debug
if(find(i)!=find(n)){
printf("orz");
return 0;
}//判断是否连通
}
cout<<ans;
return 0;
}