WA求助

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 songtj @ 2022-10-18 19:26:55

@yf0207 又改了好几处，要判断重边和自环，不过还是WA一个点，我再看看

代码：

#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,0x3f,sizeof(minn));
    minn[1] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            g[i][j] = i==j ? 0 : 0x3f3f3f3f;//这样初始化
        }
    }
    for(int i=1;i<=m;i++){
        int u,v,w;cin>>u>>v>>w;
        if (w < g[u][v]) //这里要判重边
        {
            g[u][v]=w;
            g[v][u]=w;
        }
    }
    for (int i = 1; i <= n; ++i) g[i][i] = 0; //判自环
    for (int i = 1; i <= n; ++i) minn[i] = g[1][i];
    int cat=0;
    for(int i=1;i<=n-1;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 yf0207 @ 2022-10-19 20:53:51

@songtj ACed thanks,subscribed

by songtj @ 2022-10-20 20:25:35

@yf0207

实在不好意思，前几天没时间再回复您，主要是whk太忙了，请谅解！

最后我给您改的代码还有几个问题：

• 没有判断是否会出现不连通的情况

• vis 数组的 [1] 没有初始化（实际这道题可加可不加）

给您改完的代码：

#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,0x3f,sizeof(minn));
    minn[1] = 0, vis[1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            g[i][j] = i==j ? 0 : 0x3f3f3f3f;//这样初始化
        }
    }
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        if (w < g[u][v]) //这里要判重边
        {
            g[u][v]=w;
            g[v][u]=w;
        }
    }
    for (int i = 1; i <= n; ++i) g[i][i] = 0; //判自环
    for (int i = 1; i <= n; ++i) minn[i] = g[1][i];
    int cat=-1, num=0x3f3f3f3f; //num用来记录最小值
    for(int i=1;i<=n-1;++i)
    {
        cat=-1, num=0x3f3f3f3f;
        for(int j=2;j<=n;++j)
        {
            if(!vis[j]&&(num>minn[j]))
            {
                num = minn[j]; //记录最小值
                cat=j;
            }
        }
        if (num == 0x3f3f3f3f) //如果没有比它还小的，就证明图是不连通的
        {
            puts("orz");
            return 0;
        }
        ans += num; //这里ans直接加，可以省一个循环
        vis[cat]=1;
        for(int j=2;j<=n;j++)
        {
            if(minn[j]>g[cat][j]) //在更新minn的时候是用不上vis数组的
            {
                minn[j]=g[cat][j];
            }
        }
    }
    cout<<ans; //如果联通就直接输出
    return 0;
}