yyyzrc123 @ 2023-10-08 17:11:28
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,tot,ans[100010],answer;
bool colour[10000010];
struct Node{int u,v,w;} e[100010];
bool cmp(Node a,Node b){return a.w<b.w;}
void add(int u,int v,int w){e[tot].u=u;e[tot].w=w;e[tot].v=v;tot++;}
void add2(int i){ans[cnt]=i;cnt++;}
//void print(int i){cout<<e[i].u<<' '<<e[i].v<<'\n';}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}
sort(e,e+m,cmp);
for(int i=0;i<m&&cnt<=n-1;i++){
if(colour[e[i].u]&&colour[e[i].v])continue;
add2(i);
colour[e[i].u]=colour[e[i].v]=1;
}
// for(int i=0;i<cnt;i++)print(ans[i]);
if(cnt<n-1){
cout<<"orz";
return 0;
}
for(int i=0;i<cnt;i++) answer+=e[i].w;
cout<<answer;
// cout<<"orz";
}
by yyyzrc123 @ 2023-10-08 17:17:17
by BantM @ 2023-10-08 17:20:55
不能用染色啊,算法错误
by BantM @ 2023-10-08 17:22:29
好比说
1连2
3连4
那这时1234颜色都是1,那不就连不了边了吗?可是此时树不连通啊
by yyyzrc123 @ 2023-10-09 16:43:39
@Bant_Metor 谢谢,该问题已解决,使用并查集
by yyyzrc123 @ 2023-10-09 17:07:20
过了!!!