79pts,#8.9.10TLE

C2204hyk @ 2024-07-28 20:41:11

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z,tot,ans,fa[5086];
struct ed{
    int x,y,z;
}a[100086];
int find(int x){
    while(fa[fa[x]]!=fa[x]) fa[x]=fa[fa[x]];
    return fa[x];
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
bool cmp(ed x,ed y){
    return x.z<y.z;
}
void kruskal(){
    for(int i=1;i<=m;i++){
        if(find(a[i].x) != find(a[i].y)){
            merge(a[i].x ,a[i].y );
            tot++;
            ans+=a[i].z;
            if(tot==n-1) return;
        }   
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=m;i++)
        cin>>a[i].x>>a[i].y>>a[i].z;
    sort(a+1,a+1+m,cmp);
    kruskal();
    if(tot < n-1) cout<<"orz"<<endl;
    else cout<<ans<<endl;
    return 0;
}

by lyx0813 @ 2024-07-28 21:18:50

第6行数组开小啦（2*100000）

by C2204hyk @ 2024-07-28 21:19:47

@lyx0813 OK！ 警钟敲烂！！！

by dogeandkobe @ 2024-07-28 21:28:33

菜就多练

by dogeandkobe @ 2024-07-28 21:30:46

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 400005;
struct edge {
int x, y, z;
} a[MAXN];
int fa[MAXN];
int find(int x) {
if (fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
void bin(int a, int b) {
    fa[find(b)] = fa[find(a)];
}
int n, m, ans, x, y, z, tot;
bool cmp(edge x, edge y) {
    return x.z < y.z;
}
void kruskal() {
    for (int i = 1; i <= m; i++) {
        if (find(a[i].x) != find (a[i].y)) {
            bin(a[i].x, a[i].y);
            tot++;
            ans += a[i].z;
        }
    }
}
int mian() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    sort(a+1,a+1+m,cmp);
    kruskal();
    if(tot<n-1) cout<<"orz";
    else cout<<ans;
    return 0;

}

by 0Io_oI0 @ 2024-07-31 12:33:01

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,k=0,sum=0;
struct edge{
    int u,v,w;
}e[200005],mst[200005];
bool cmp(edge a,edge b){
    if(a.w<b.w)return 1;
    else return 0;
}
int a[200005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=i;
    for(int i=0;i<m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e,e+m,cmp);
    for(int i=0;i<m;i++){
        if(a[e[i].u]!=a[e[i].v]){
            k++;
            mst[k].u=e[i].u;
            mst[k].v=e[i].v;
            mst[k].w=e[i].w;
            sum+=e[i].w;
            int s=min(a[e[i].u],a[e[i].v]);
            if(s==a[e[i].u]){
                for(int j=0;j<m;j++)
                    if(a[j]==a[e[i].v]&&j!=e[i].v)a[j]=s;
                a[e[i].v]=s;
            }
            else{
                for(int j=0;j<m;j++)
                    if(a[j]==a[e[i].u]&&j!=e[i].u)a[j]=s;
                a[e[i].u]=s;
            }
            if(k==n-1)break;
        }
    }
    if(k<n-1)cout<<"orz";
    else cout<<sum;
    return 0;
}

如果AC了给个关注呗

by C2204hyk @ 2024-08-02 17:51:04

@0Io_oI0 包的啊