抄都抄不对？标准的板子代码啊

Mr_LiuXinan @ 2024-08-15 20:36:01

#include <iostream>
using namespace std;

const int INF = 0x7fffffff;
int n, m, ans;
int g[5001][5001];
int dist[5001];
int book[5001];

void primMST()
{
    dist[1] = 0;
    book[1] = 1;

    for (int i = 2; i <= n; ++i)
        dist[i] = min(dist[i], g[1][i]);
    for (int i = 2; i <= n; ++i)
    {
        int tmp = INF;
        int t = -1;
        for (int j = 2; j <= n; ++j)
        {
            if (!book[j] && dist[j] < tmp)
            {
                tmp = dist[j];
                t = j;
            }
        }
        if (t == -1)
        {
            ans = INF;
            return;
        }
        book[t] = 1;
        ans += dist[t];
        for (int j = 2; j <= n; ++j)
            dist[j] = min(dist[j], g[t][j]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        dist[i] = INF;
        for (int j = 1; j <= n; ++j)
            g[i][j] = INF;
    }

    int x, y, z;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> z;
        g[x][y] = z;
        g[y][x] = z;
    }

    primMST();

    if (ans == INF)
        cout << "orz";
    else
        cout << ans;

    return 0;
}

by Yzh929 @ 2024-08-15 20:54:03

蒟蒻代码理解能力差，只能帮你到这了

//利用了并查集的思想

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int n,m,fa[N],ans,cnt;
struct qq
{
    int x,y,z;//代表前后连接节点的权值 
} t[N];
bool cmp(qq a,qq b)//按边权从小大大排序
{
    return a.z<b.z;
}
int find(int i)//寻找父节点 
{
    if(fa[i]==i)
    {
        return i;
    }
    return fa[i]=find(fa[i]); //递归
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;//初始化每个集合无交集，即自己是自己的父亲
    for(int i=1;i<=m;i++)
    {
        cin>>t[i].x>>t[i].y>>t[i].z;
    }
    sort(t+1,t+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int x1=find(t[i].x);//记录父亲，方便以后用
        int y1=find(t[i].y);
        if(x1!=y1)
        {
            fa[x1]=y1;//将两个集合合并，即搞成同一个父节点
            ans+=t[i].z;
            cnt++;
        }

    }if(cnt<n-1)
        {
            cout<<"orz"<<endl;

            return 0;
        }
    cout<<ans<<endl;
    return 0;
}

by mingliu_sun @ 2024-08-15 20:56:08

yzh真是太善良了

by Yzh929 @ 2024-08-15 20:57:10

我不太理解您用邻接矩阵写的代码，您可以先看着这篇并查集的(#^.^#)

by Mr_LiuXinan @ 2024-08-16 07:49:48

@Yzh929 谢谢你的帮助，不过我是想知道我这个算法错在哪。这个我昨天刚学的，并查集说是用于Kruskal算法，我这个邻接矩阵是用的另一种Prim算法，去CSDN搜Prim算法的话会发现我这个就是照它上面敲的，简直一毛一样。

by BJqxszx_zhuyukun @ 2024-08-16 16:12:30

@Mr_LiuXinan prim也能用邻接表写

by Mr_LiuXinan @ 2024-08-16 17:27:15

@BJqxszx_zhuyukun 嗯嗯，但就是不知道我现在这种写法哪里出问题了

by BJqxszx_zhuyukun @ 2024-08-16 18:36:59

@Mr_LiuXinan 对不起，我太蒻了，查不出来了

by BJqxszx_zhuyukun @ 2024-08-16 18:39:57

@Mr_LiuXinan 对不起，我太蒻了，查不出来了

by Mr_LiuXinan @ 2024-08-16 19:07:06

@BJqxszx_zhuyukun 谢谢，我知道问题了，输入的部分改成这样就A了

for (int i = 1; i <= m; ++i){
  cin >> x >> y >> z;
  if (x == y)
    continue;
  g[x][y] = min(z, g[x][y]);
  g[y][x] = g[x][y];
}