为什么这样写 WA on #7
int kruskal(LL mid){
vec.clear();
int cnt=0;
for(int i=1;i<=m;i++){
if(a[i].x==1){
a[i].c+=mid;
}
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y;
int tx=get(x),ty=get(y);
if(tx!=ty){
fa[tx]=ty;
vec.push_back(a[i].id);
if(x==1){
cnt++;
}
}
}
for(int i=1;i<=m;i++){
if(a[i].x==1){
a[i].c-=mid;
}
}
return cnt<=K;
}
for(int i=1;i<=m;i++){
scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].c);
if(a[i].x>a[i].y){
swap(a[i].x,a[i].y);
}
a[i].id=i;
}
而这样写 WA on #8
int kruskal(LL mid){
vec.clear();
int cnt=0;
for(int i=1;i<=alen;i++){
e[i]=a[i];
e[i].c+=mid;
}
for(int i=1;i<=blen;i++){
e[i+alen]=b[i];
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int x=e[i].x,y=e[i].y;
int tx=get(x),ty=get(y);
if(tx!=ty){
fa[tx]=ty;
vec.push_back(e[i].id);
if(x==1){
cnt++;
}
}
}
return cnt<=K;
}
for(int i=1;i<=m;i++){
int x,y;LL c;scanf("%d%d%lld",&x,&y,&c);
if(x>y)swap(x,y);
if(x==1)a[++alen]={x,y,i,c};
else b[++blen]={x,y,i,c};
}