GGapa @ 2023-07-12 15:56:12
//P3366 【模板】最小生成树
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn=2e5+5;
int n,m;
struct EDGE//dui
{
int left,right;
int value;
};
EDGE edge[maxn];
int father[maxn];
int succeed=0,ans=0;
int read()//right
{
int f=1,x=0;
char c;
c=getchar();
if(c=='-')f=-1,c=getchar();
while('0'<=c&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
bool cmp(EDGE x,EDGE y) //right
{
return x.value<y.value;
}
int find(int it)//right
{
if(it==father[it])return it;
else return father[it]=find(father[it]);
}
int main()
{
n=read(),m=read();
for(int i = 1;i<=n;i++)father[i]=i;
for(int i = 1;i<=m;i++)
{
edge[i].left=read();
edge[i].right=read();
edge[i].value=read();
}
sort(edge+1,edge+1+m,cmp);
for(int i = 1;i<=m;i++)
{
int findl=find(edge[i].left),findr=find(edge[i].right);
if(findl!=findr)
{
father[findr]=findl;
succeed++;ans+=edge[i].value;
}
if(succeed>=n-1)
{
cout<<ans<<endl;
return 0;
}
}
printf("orz\n");
return 0;
}
by 六楼溜刘 @ 2023-07-12 16:22:56
@spider_oyster 感觉不如这个
int read(){
int x;cin>>x;return x;
}
by spider_oyster @ 2023-07-12 16:24:08
@六楼溜刘 为什么不是:
inline rd()
{
...
}
by 六楼溜刘 @ 2023-07-12 16:25:47
@spider_oyster @GMJoanna 这个b去年CSPS全这样写的直接爆0了
by GGapa @ 2023-07-12 22:13:26
谢谢各位神犇,问题解决了