1 条题解

  • 0
    @ 2019-09-24 21:15:08

    #include<bits/stdc++.h>
    using namespace std;
    int n,m,f[10010],x[10010],y[10010];
    double ans=0,total=0;
    //虽然要切掉每一个环的最小边 不过我们不需要在怎么解环上下功夫(其实是我环这一块没学好)
    //我们可以倒过来看 当我们切掉所有的最小边时 剩下的是不是就成了一个最大生成树???
    //最大生成树的做法和最小生成树一样 只有一个小点需要改
    //所以要得出结果 我们就可以用总边权减去最大生成树
    struct node
    {//结构体
    int next;//上一个点
    int to;//下一个点
    double dis;//距离
    }P[20010];
    double distance(int a,int b)
    {//一小段的代码原本一开始我只是为了避免在主函数里写的时候看的麻烦
    //但是之后在走的时候发现这样会出现库问题 不让过 所以写在这里提醒你们一下
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
    }
    bool cmp(node a,node b)
    {//这里注意要从大到小来排序 因为要做最大生成树
    return a.dis>b.dis;
    }
    int find(int x)
    {//并查集
    if(f[x]==x) return x;
    return find(f[x]);
    }
    void Kruskal()
    {//Kruskal模板
    int check=0;
    for(int i=1;i<=m;i++)
    {
    int f1=find(P[i].next);
    int f2=find(P[i].to);
    if(f1!=f2)
    {
    ans+=P[i].dis;
    f[f1]=f2;
    check++;
    if(check==n-1) break;
    }
    }
    }
    int main()
    {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    f[i]=i;//初始化
    cin>>x[i]>>y[i];//坐标
    }
    for(int i=1;i<=m;i++)
    {
    cin>>P[i].next>>P[i].to;
    P[i].dis=sqrt((x[P[i].next]-x[P[i].to])*(x[P[i].next]-x[P[i].to])+(y[P[i].next]-y[P[i].to])*(y[P[i].next]-y[P[i].to]));
    total+=P[i].dis;
    }
    sort(P+1,P+m+1,cmp);
    Kruskal();
    cout<<fixed<<setprecision(10)<<total-ans<<endl;
    return 0;
    //当时我在做的时候虽然样例都过了 但是在vojis却wa了 最后听老师说数据有问题 得拿去特判
    //不知道当你们看到这篇题解的时候 数据拿去特判了没
    //不过在石光oj上去测的时候拿到了40分 还有一个可恶的315大佬 暴力并查集拿了50分 气死我了
    }
    //来自某届石光中学信竞苟蒻学长 愿看到此文的你 努力码题 为校争光

  • 1

信息

难度
10
分类
(无)
标签
递交数
27
已通过
0
通过率
0%
被复制
1
上传者