文章

3

粉丝

36

获赞

6

访问

2.2k

头像
kruskal模板的简洁写法
P1611 中山大学机试题
发布于2023年6月29日 15:56
阅读数 600

 

#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...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发