题目【USACO 2007 Dec S】 Building Roads

链接

先贴惨状

alt

这么一大片的段错误，没错，就是犯了你所想的那样最愚蠢的错误————数组开小了。

没仔细读题，代码实现的过程中数组开小了，反复检查了很多遍，还认为自己没有错，最后发现竟然是这个问题，气的我分号都没打就提交了，于是ce了（乐）。

让人桑心的是，加了分号以后，竟然还wa了两发，后面意识到了是结构体排序那里的错误。

再就是sqrt那里的精度问题，就这几个错误，希望大家也注意。

不多说，上思路

是一道一读就知道要用最小生成树的题（嘤嘤嘤，伦家只会写这种啦）该说不说翻译要了我点时间（数组越界问题就是这么来的，哭）

ok既然是最小生成树，那必然是要排序的，因此我们需要一个结构体数组，存入每个点与每个点之间的距离，再来选取最适合添加的道路，至于已经连通的道路？赋0就行了啦大叔。

思路就到这里吧，嗯？什么？你说为什么没了？拜托，这真的只是一道用了浮点数的板子题啦（所以我为什么错这么多次？）

咳咳，抛开我菜不谈，该上代码了

因为有点烦重名，所以没有使用std的命名空间，个人喜好啦。

#define ll long long
#define endl "\n"
const int MAX=1e6+5;
int n,m;
int f[MAX];//这个作用懂得都懂
int x[MAX],y[MAX];//存储每个点的位置信息
struct kk{
    int x,y;
    double dis;
}pp[MAX];//distance 距离

bool cmp(kk x, kk y){
	if (x.dis == y.dis) return x.x < y.x;//关于因为缺少这一条语句而wa了一发这件事
	return x.dis < y.dis;//最小，自然是升序排序
}

int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);//划重点
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0),std::cout.tie(0);
    std::cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++){
        std::cin>>x[i]>>y[i];
        f[i]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            pp[++cnt].x=i;
            pp[cnt].y=j;
            pp[cnt].dis=(double)(sqrt((double)(x[i]-x[j])*(x[i]-x[j])+(double)(y[i]-y[j])*(y[i]-y[j])));
        }//注意double！！！
    }
    for(int i=1;i<=m;i++){
        int v,u;
        std::cin>>v>>u;
        pp[++cnt].x=v;
        pp[cnt].y=u;
        pp[cnt].dis=0;
    }
    std::sort(pp+1,pp+cnt+1,cmp);
    double sum=0.0;
    int ans=0;
    for(int i=1;i<=cnt;i++){
        if(find(pp[i].x)!=find(pp[i].y)){
            f[find(pp[i].x)]=find(pp[i].y);//很多地方都想加注释，结果似乎真的没啥好说的
            sum+=pp[i].dis;//这题真的太板子了，我真的是太菜了
        }
    }
    std::cout<<std::fixed<<std::setprecision(2)<<sum<<endl;
    return 0;
}

划重点那里，是希望如果有人和我一样查找还不会用递归的，请一定记下来背死了，不然会超时，还会被学长训（小声bb）

好了，到此为止了，大概写了有一个礼拜了，现在才来写博客，没办法，太懒了，如果看到了这里，祝你cf上大分！