#8#9#10#13求条

syd190214 @ 2024-12-11 19:43:04

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll M=3005;
ll n,m;
ll g[M][M];
ll dist[M];
bool st[M];
ll Prim(){
    int res=0;
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0; 
    for(ll i=0;i<n;i++){
        int t=-1;
        for(ll j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }
        st[t]=true;
        if(dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;
        res+=dist[t];
        for(int j=1;j<=n;++j)dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}
int main(){
    ll i;
    scanf("%lld%lld",&n,&m);
    memset(g,0x3f,sizeof(g));
    for(i=0;i<m;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    ll prim=Prim();
    if(prim==0x3f3f3f3f) printf("orz");
    else cout<<prim;
    return 0;
}

by masonxiong @ 2024-12-11 19:51:10

@syd190214

1. 数组开小了。
2. 开大了会 MLE，你应当使用邻接表。

by Terrible @ 2024-12-11 19:52:49

@syd190214

换用 int，然后把极大值改为 0x7f7f7f7f，memset 采用 0x7f 低位一字节赋值。0x7f7f7f7f= 2139062143。

#include <iostream>
#include <bits/stdc++.h>
#define ll int
using namespace std;
const ll M=5005;
ll n,m;
ll g[M][M];
ll dist[M];
bool st[M];
ll Prim(){
    int res=0;
    memset(dist,0x7f,sizeof(dist));
    dist[1]=0; 
    for(ll i=0;i<n;i++){
        int t=-1;
        for(ll j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
        }
        st[t]=true;
        if(dist[t]==0x7f7f7f7f) return 0x7f7f7f7f;
        res+=dist[t];
        for(int j=1;j<=n;++j)dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}
int main(){
    ll i;
    scanf("%d%d",&n,&m);
    memset(g,0x7f,sizeof(g));
    for(i=0;i<m;i++){
        ll x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        g[x][y]=g[y][x]=min(g[x][y],z);
    }
    ll prim=Prim();
    if(prim==0x7f7f7f7f) printf("orz");
    else cout<<prim;
    return 0;
}

依然建议学习题解的方法。

by Terrible @ 2024-12-11 19:55:00

洛谷上的内存限制都太小了，都快 2025 年了，连个 512MB 都不给，压缩内存意义不是很大。

by syd190214 @ 2024-12-11 19:56:35

@Terrible 楼上的dalao看不懂，邻接表没学 thanks

by syd190214 @ 2024-12-11 19:57:57

@Terrible 已经AC