16分 prim算法 HELP！！！

jiangbaolin @ 2024-10-09 17:27:21

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,z,a[15001][15001],b[100001],h,c,mi,s;
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            a[i][j]=0x7fffffff;
        }
    }
    for(int i=1;i<=m;i++){
        cin >> x >> y >> z;
        a[x][y]=min(a[x][y],z);
        a[y][x]=min(a[y][x],z);
    }
    for(int i=1;i<=n;i++){
        b[i]=a[1][i];
        if(b[i]==0){
            b[i]=0x7fffffff;
        }
    }
    b[1]=0;
    for(int i=2;i<=n;i++){
        mi=0x7fffffff;
        for(int j=1;j<=n;j++){
            if(mi>b[j] && b[j]!=0){
                mi=b[j];
                h=j;
            }
        }
        b[h]=0;
        a[h/n+1][h%n]=0;
        a[h%n][h/n+1]=0;
        for(int j=1;j<=n;j++){
            if(b[i]!=0 && a[h%n][j]!=0){
                b[j]=min(b[j],a[h%n][j]);
            }
        }
        s=s+mi;
    }
    if(s<0x7fffffff && s!=0){
        cout << s;
    }
    else{
        cout << "orz";
    }
    return 0;
}

by _liujunming_ @ 2024-11-10 16:32:36

@jiangbaolin

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
bool f[N];
int d[N];
struct node
{
    int to;
    int val;
};
vector<node> v[N];
int ans=0;
int n,m;
void prim()
{
//  f[1]=1;
    for(int i=1;i<=n;i++)d[i]=INT_MAX;
    d[1]=0;
    for(int i=1;i<=n;i++)
    {
        int minn=INT_MAX,u=-1;
        for(int j=1;j<=n;j++)
            if(!f[j]&&d[j]<minn)minn=d[j],u=j;
        if(u==-1)break;
        ans+=minn;
        f[u]=1;
        for(int j=0;j<v[u].size();j++)
            if(!f[v[u][j].to]&&d[v[u][j].to]>v[u][j].val)d[v[u][j].to]=v[u][j].val;
    }
    for(int i=1;i<=n;i++)
    {
        if(!f[i])
        {
            printf("orz");
            exit(0);
        }
    }
    printf("%d",ans);
}
int main()
{
    ios::sync_with_stdio(0);
    scanf("%d%d",&n,&m);
    memset(f,false,sizeof(f));
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        node r={b,c},rr={a,c};
        v[a].push_back(r);
        v[b].push_back(rr);
    }
    prim();
    return 0;
}

by jiangbaolin @ 2024-11-11 16:04:34

谢谢

by huangjy2012 @ 2024-11-11 16:27:11

@jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin @jiangbaolin