WA求助

P3366 【模板】最小生成树

yf0207 @ 2022-10-18 18:43:20

#include <bits/stdc++.h>
using namespace std;
const int N=5100;
int n,m,ans,g[N][N],minn[N];
bool vis[N];
int main()
{
    std::ios::sync_with_stdio(0);
    cin>>n>>m;
    memset(minn,0x3f3f3f,sizeof(minn));
    memset(vis,0,sizeof(vis));
    memset(g,0x3f3f3f,sizeof(g));
    for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[u][v]=w;g[v][u]=w;}
    int cat=0;
    for(int i=1;i<=n;i++)
    {
        cat=0;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&(minn[cat]>minn[j]))
            {
                cat=j;
            }
        }
        vis[cat]=1;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&(minn[j]>g[cat][j]))
            {
                minn[j]=g[cat][j];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        ans+=minn[i];
    }
    cout<<ans;
    return 0;
}

by ssytxy2024 @ 2022-10-18 18:47:06

排序呢?


by ssytxy2024 @ 2022-10-18 18:47:24

哦你是prim啊,那没事了


by yf0207 @ 2022-10-18 18:48:06

然后如何判断-1呢


by songtj @ 2022-10-18 18:54:00

@yf0207

您的 memset 用错了,memset 是按字节赋值,不能这么用。

如果要赋极大值,可以改成

memset(a, 0x3f, sizeof(a));

by yf0207 @ 2022-10-18 18:55:47

but 还是WA了


by yf0207 @ 2022-10-18 18:55:59

@songtj


by songtj @ 2022-10-18 18:56:13

@yf0207 是的,还有其他错,我正在看


by songtj @ 2022-10-18 19:01:10

@yf0207 还有,您的 minn 数组应该在赋极大值之后把 [1] 设为0


by yf0207 @ 2022-10-18 19:03:28

又双 WA 了


by yf0207 @ 2022-10-18 19:05:26

谢谢


| 下一页