@[Rannan2000](/user/1044332) 虽然是WA,但是还是要提醒你的并查集写错了。
by Xile @ 2023-12-07 21:47:17
@[Rannan2000](/user/1044332) find应该是
```cpp
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);//路径压缩
}
```
因为这道题数据小,所以你没有T
by Xile @ 2023-12-07 21:48:27
@[Rannan2000](/user/1044332) 而且你的建边有问题
by Xile @ 2023-12-07 21:51:43
@[Xile](/user/428889) 谢谢
~~太久没打生疏了。。~~
by Three_no @ 2023-12-07 22:03:49
```cpp
#include<bits/stdc++.h>
using namespace std;
int a,b,cost,fa[1000],mst,num,ans,k;
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);//路径压缩
}
struct node{
int u,v,w;
}edge[200000];
bool cmp(node a,node b){
return a.w<b.w;
}
int main(){
cin>>a>>b;
for(int i=1;i<=b;i++){
for(int j=1;j<=b;j++){
cin>>cost;
if(i>=j||cost==0)continue;
//edge[++k].u=i;
//edge[k].v=j;
//edge[k].w=cost;
edge[++k]={i,j,cost};
if(edge[i].w>a)num++;
}
}
sort(edge+1,edge+k+1,cmp);
for(int i=1;i<=b;i++){
fa[i]=i;
}
for(int i=1;i<=k-num;i++){
int fx=find(edge[i].u);
int fy=find(edge[i].v);
if(fx!=fy){
fa[fx]=fy;
mst+=edge[i].w;
ans++;
}
}
if(ans==b-1) cout<<mst+a;
else cout<<mst+(b-ans)*a;
return 0;
}
```
改成这样就ac了
,发现是排序错了
by Three_no @ 2023-12-07 22:12:29