洛谷[テンプレート]最小生成ツリー
3128 ワード
タイトルリンク:https://www.luogu.org/problemnew/show/P3366ここでは説明しない
#include
#include
#include
#include
#include
using namespace std;
int n,m,fa[5010],ans=0,flag=0;
struct node
{
int u,v,c;
} p[200010];
int get(int a)
{
if(a==fa[a])
return a;
else
return fa[a]=get(fa[a]);
}
bool cmp(node ar,node br)
{
return ar.cint main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
fa[i]=i;
for(int i=1; i<=m; i++)
scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].c);
sort(p+1,p+1+m,cmp);
for(int i=1; i<=m; i++)
{
int x=p[i].u,y=p[i].v;
int fx=get(x),fy=get(y);
if(fx!=fy)
{
ans+=p[i].c;
fa[fx]=fy;
}
}
for(int i=1; i<=n; i++)
{
if(fa[i]==i)
{
flag++;
if(flag==2)
break;
}
}
if(flag==2)
printf("orz");
else
printf("%d",ans);
return 0;
}