社区讨论
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 条回复,欢迎继续交流。
正在加载回复...