KRUSKAL求助

回复帖子

@zhaozhaoxueba 2019-12-02 23:38 回复

算法kruskal,得分40,详情

代码见下:

#include<bits/stdc++.h>
using namespace std;

struct edge
{
    int x,y,z;
} e[5005];

int n,m;
int u,v,fu,fv,cnt,ans;
int fa[5005];

bool cmp(edge a,edge b)
{
    return a.z < b.z || (a.z==b.z && a.x<b.x);
}

/*int find(x)
{
    if(x == fa[x]) return x;
    else
        fa[x] = find(fa[x]);
}*/
int findf(int x)
{
    return x == fa[x]?x:fa[x]=findf(fa[x]);
}

void kruskal()
{
    for(int i=1;i<=m;i++)
        fa[i] = i;
    for(int i=1;i<=n;i++)
    {
        u = e[i].x;
        v = e[i].y;
        fu = findf(u);
        fv = findf(v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans += e[i].z;
            cnt++;
        }
        if(cnt == m-1) break;
    }
}

int main()
{
    //freopen("prim.in","r",stdin);
    //freopen("kruopen.txt","w",stdout);
    cin >> m >> n;
    for(int i=1;i<=n;i++)
        cin >> e[i].x >> e[i].y >> e[i].z;
    sort(e+1,e+n+1,cmp);
    kruskal();
    if(ans) cout << ans;
    else cout << "orz";
    return 0;
}

想知道哪里出错了,以及如何改正!比较急。

谢谢!

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。