clx201022 @ 2023-03-12 11:18:10
样例 input 4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3 my output 9 应该是七的
#include<bits/stdc++.h>
using namespace std;
struct bingchaji
{
int f[5001],size[5001];
inline int find(int x)
{
//return f[x]==x?x:f[x]=find(f[x]);
while(x!=f[x])
x=f[x]=f[f[x]];
return x;
}
inline void merge(int x,int y)
{
x=find(x);
y=find(y);
if(size[x]>size[y])swap(x,y);
f[x]=y;
size[y]+=size[x];
}
bingchaji(int n)
{
for(int i=0;i<=n;i++)
{
f[i]=i;
size[i]=1;
}
}
};
struct Edge
{
int to,w,start;
};
vector<Edge>e;
inline bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int n,m,ans,bian;
int main()
{
cin>>n>>m;
bingchaji a(n);
for(int i=1;i<=m;i++)
{
Edge bian;
cin>>bian.start>>bian.to>>bian.w;
e.push_back(bian);
}
sort(e.begin(),e.end(),cmp);
for(int i=1,u,v;i<=m;i++)
{
u=a.find(e[i].start);
v=a.find(e[i].to);
if(a.find(e[i].start)==a.find(e[i].to))continue;
ans+=e[i].w;
a.merge(u,v);
bian++;
if(bian==n-1)break;
}
cout<<ans;
return 0;
}
求调
by ZZQF5677 @ 2023-03-12 11:33:33
好像也好少了orz
by clx201022 @ 2023-03-12 11:35:52
@ZZQF5677 对啊,但样例里没有orz,求样例错误原因
by clx201022 @ 2023-03-12 14:16:09
AC了,AC了