社区讨论

70分

P3366【模板】最小生成树参与者 5已保存回复 10

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
10 条
当前快照
1 份
快照标识符
@mi6u1vhn
此快照首次捕获于
2025/11/20 10:49
4 个月前
此快照最后确认于
2025/11/20 10:49
4 个月前
查看原帖
CPP
近日水 _货车运输_ 时打崩了(70分);
过来打模板果然错了,仅70分QAQ;
2,9,10 输出全是**orz**;
求教,^_^;
CPP
#include <cstdio>
#include <algorithm>
#define RI register int
using namespace std;
int n,m,k,x,y,z,sw,ans;
struct node{
    int s,to,nx,w;
}e[100010];
int head[10010],cnte,cnt;
bool vis[10010];
int f[10010];
inline bool cmp(node a,node b){
    if(a.w!=b.w)    return a.w<b.w;
    if(a.s!=b.s)    return a.s<b.s;
    return a.to<b.to;
}
inline int find(int x){
    return f[x]=(f[x]==x)?x:find(f[x]);
}
inline void read(int &x){
    x=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());;
    for(;ch<='9'&&ch>='0';x=(x<<1)+(x<<3)+ch-'0',ch=getchar());
}
inline void add(int u,int v,int w){
    e[++cnte].to=v,e[cnte].s=u,e[cnte].w=w,e[cnte].nx=head[u],head[u]=cnte;
}
inline void shu(){
    for(RI i=1;i<=n;++i) f[i]=i;
    sort(e+1,e+cnte+1,cmp);int u,v;
    for(RI i=1;i<=cnte&&cnt<=n-1;++i){
        if(find(e[i].s)!=find(e[i].to))
        ++cnt,ans+=e[i].w,f[f[e[i].s]]=f[e[i].to];
    }
    if(cnt==n-1)    printf("%d",ans);
    else printf("orz");
}
int main(){
    read(n),read(m);
    for(RI i=1;i<=m;++i)
        read(x),read(y),read(z),add(x,y,z),add(y,x,z);
    shu();
}

回复

10 条回复,欢迎继续交流。

正在加载回复...