为什么在这道最小生成树的题中,我用
#include <iostream>
#include <algorithm>
using namespace std;
struct bian{
int u,v,w;
}a[10005];
int n,k;
int fa[2005];
bool cmp(bian x,bian y){
return x.w<y.w;
}
int fnd(int u_){
if(fa[u_]==u_)
return fa[u_];
return fa[u_]=fnd(fa[u_]);
}
void merge(int u_,int v_){
fa[fnd(u_)]=fnd(v_);
}
int kruskal(){
for(int i=1;i<2005;i++)
fa[i]=i;
sort(a+1,a+k+1,cmp);
int res=0;
for(int i=1;i<=k;i++){
if(fnd(a[i].u)==fnd(a[i].v))
continue;
merge(a[i].u,a[i].v);
res+=a[i].w;
}
return res;
}
int main(){
cin>>n>>k;
int ans=0;
for(int i=1,op,u_,v_,w_;i<=k;i++){
cin>>op>>u_>>v_>>w_;
if(op==1)
ans+=w_,merge(u_,v_);
else
a[i]={u_,v_,w_};
}
ans+=kruskal();
cout<<ans<<endl;
return 0;
}
会wa。
而把初始化fa数组放到主函数里却AC了?
ACcode:
#include <iostream>
#include <algorithm>
using namespace std;
struct bian{
int u,v,w;
}a[10005];
int n,k;
int fa[2005];
bool cmp(bian x,bian y){
return x.w<y.w;
}
int fnd(int u_){
if(fa[u_]==u_)
return fa[u_];
return fa[u_]=fnd(fa[u_]);
}
void merge(int u_,int v_){
fa[fnd(u_)]=fnd(v_);
}
int kruskal(){
sort(a+1,a+k+1,cmp);
int res=0;
for(int i=1;i<=k;i++){
if(fnd(a[i].u)==fnd(a[i].v))
continue;
merge(a[i].u,a[i].v);
res+=a[i].w;
}
return res;
}
int main(){
for(int i=1;i<2005;i++)
fa[i]=i;
cin>>n>>k;
int ans=0;
for(int i=1,op,u_,v_,w_;i<=k;i++){
cin>>op>>u_>>v_>>w_;
if(op==1)
ans+=w_,merge(u_,v_);
else
a[i]={u_,v_,w_};
}
ans+=kruskal();
cout<<ans<<endl;
return 0;
}