社区讨论
C++只过了最后一个点,蒟蒻求调
P3366【模板】最小生成树参与者 4已保存回复 14
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 14 条
- 当前快照
- 1 份
- 快照标识符
- @lo29ar16
- 此快照首次捕获于
- 2023/10/23 10:06 2 年前
- 此快照最后确认于
- 2023/11/03 10:18 2 年前
CPP
//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;
}
回复
共 14 条回复,欢迎继续交流。
正在加载回复...