EOJ3247:铁路修复计划

传送门

题意

分析

这题用二分做就好啦，有点卡常数，改了几下for的次数

套了个板子，连最小生成树都忘记了QAQ

trick

代码

    #include<cstdio>

    #include<iostream>

    #include<cstring>

    #include<algorithm>

    using namespace std;

    const int Maxn=100100;

    const double eps = 1e-7;

    #define ll long long

    int p[Maxn];

    int find(int x)

    {

        return p[x] == x ? x : p[x] = find(p[x]);

    }//并查集

    struct node

    {

        int u,v,f;

        double w;

        bool operator<(const node &p)const

        {

            return w<p.w;

        }

    }q[100100];//每条边的情况，u,v是边的端点，w是边的权值

    int main()

    {

        int n,m,x,y;

        double sum1,sum2,M;

        while (scanf("%d %d %lf",&n,&m,&M)==3)

        {

            for (int i = 0; i < m; ++i)

            {

                scanf("%d%d%lf%d",&q[i].u,&q[i].v,&q[i].w,&q[i].f);//不需要考虑重边的情况，因为重边的存在并不覆盖

                //之前的边，重边参与排序，选出重边中最小的，就算遍历到了重边中较大的，此时端点已经在同

                //一棵树中了，所以重边的存在不会有影响

            }

            sum1=sum2=0;

            int num=0;

            double l=1,r=1e10;

            for(int i=1;i<=100;++i){

            for (int j = 1; j <= n; ++j) p[j] = j;

            double mid=(l+r)/2;

            sum1=sum2=0;

            for(int j=0;j<m;++j) if(q[j].f) q[j].w*=mid;

            sort(q,q+m);

            for (int j = 0; j < m; ++j)//m条边，从其中选出n-1条边，然后跳出循环

            {

                x = find(q[j].u);

                y = find(q[j].v);

                if (x != y)

                {

                    if (x > y)

                        p[x] = y;

                    else

                        p[y] = x;

                    if(q[j].f) sum1+=q[j].w;else sum2+=q[j].w;

                    ++num;

                }

                if (num == n-1) break;

            }

            if(sum1+sum2<M-eps) l=mid;else r=mid;

            //printf("%f %f %f\n",sum1,sum2,mid);

            for(int j=0;j<m;++j) if(q[j].f) q[j].w/=mid;

            }

            printf("%f\n",(l+r)/2);

        }

        return 0;

    }