文章
3
粉丝
36
获赞
6
访问
3.2k
#include<iostream>
#include<algorithm>
using namespace std;
struct edge
{
int a, b, w;
bool operator<(const edge& e) const
{
return w<e.w;
}
};
const int M = 200010, N = 5010;
int n,m;
edge e[M];
int p[N];
int find(int x) // 并查集
{
if(p[x]!=x) p[x] = find(p[x]);
return p[x];
}
void kruskal()
{
sort(e,e+m);
for(int i=0;i<=n;i++) p[i] = i; //初始化并查集
int res = 0,cnt = 0;
for(int i=0;i<m;i++)
{
int a=e[i].a, b=e[i].b, w=e[i].w;
a = find(a), b = find(b);
if(a!=b)
{
p[a] = b;
res+=w;
cnt++;
}
}
if(cnt==n-1) cout<<res<<endl;
else cout<<"orz"<<endl;
}
int main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int a,b,w;
cin>>a>>b>>w; // 重边不影响算法的正确性
e[i] = {a,b,w};
}
kr...
登录后发布评论
暂无评论,来抢沙发