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 GGapa @ 2023-07-12 15:58:21
我去下载了一个样例来看,自测发现并没有问题:
input
5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419
output:
729
测试记录
by GGapa @ 2023-07-12 16:01:27
@GGapa 是测试点1
by FTR_CLCX @ 2023-07-12 16:03:10
@GGapa 你洛谷在线IDE试试
by FTR_CLCX @ 2023-07-12 16:03:48
@GGapa 本地和洛谷评测机输出有可能不同
by 六楼溜刘 @ 2023-07-12 16:04:06
@GGapa 快读写错了
by 六楼溜刘 @ 2023-07-12 16:04:20
@GGapa 看看我的
by 六楼溜刘 @ 2023-07-12 16:04:45
#define gc getchar()
inline int read(){
int x=0,f=1;char c;
while(!isdigit(c=gc)) if(c=='-') f=-1;
while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
return x*f;
}
#undef gc
by 六楼溜刘 @ 2023-07-12 16:07:11
你把空字符(比如换行 \n
)当数字读了,但 Windows 默认忽略空字符,Linux 不会忽略
by 六楼溜刘 @ 2023-07-12 16:08:33
所以你本地没问题传上去有问题
by spider_oyster @ 2023-07-12 16:20:24
@六楼溜刘 别人大括号要还行,不如我的
inline int rd()
{
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}