求助,kruskal写挂了,90分

回复帖子

@Ymw123  2020-09-16 20:48 回复

RT

#include <iostream>
using namespace std;
int find_father(int x);
void build(int x,int y,int z);
void kp(int l,int r);
void kruskal();
void read();
void out();
struct tree{
    int u,v,data;
}edge[500001];
int f[500001],A,B,m = 0,edge_num = 0,edge_t = 0;
int main(){
    read();
    kp(1,m);
    kruskal();
    out();
    return 0;
}
int find_father(int x){
    if(f[x] == x)
       return x;
    return f[x] = find_father(f[x]);
}
void build(int x,int y,int z){
    m++;
    edge[m].u = x;
    edge[m].v = y;
    edge[m].data = z;
}
void kp(int l,int r){
    int i = l,j = r,mid = edge[(l+r)/2].data;
    do{
        while(edge[i].data < mid)i++;
        while(edge[j].data > mid)j--;
        if(i <= j){
            swap(edge[i],edge[j]);
            i++;
            j--;
        }
    }while(i <= j);
    if(i < r)kp(i,r);
    if(l < j)kp(l,j);
}
void kruskal(){
    for(int i = 1;i <= m;i++){
        if(find_father(edge[i].u) != find_father(edge[i].v)){
            f[find_father(edge[i].u)] = find_father(edge[i].v);
            edge_t++;
            edge_num += edge[i].data;
        }
        if(edge_t == B - 1)
            break;
    }
    edge_num += A;
}
void read(){
    cin >> A >> B;
    int x;
    for(int i = 1;i <= B;i++){
        for(int j = 1;j <= B;j++){
            cin >> x;
            if(i < j && x != 0)
                build(i,j,x);
        }
    }
    for(int i = 1;i <= B;i++)
       f[i] = i;
}
void out(){
    cout << edge_num << endl;
}
@Ymw123  2020-09-16 20:54 回复 举报

另外告诫后人,这题所谓的优惠并不一定比 $A$ 要小

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。