【bzoj2654】tree（二分+MST）

好神奇的一道题

我们发现给白边加上权值后 跑MST后 选到的白边就越少

然后就二分这个加上的权值

不过边界好像有点恶心？不过没关系 思想最重要

#include<bits/stdc++.h>
#define N 50005
#define M 100005
using namespace std;
struct Edge
{
    int from,to,color,val;
}edge[M];
template <class T>
inline void read(T &x)
{
    x=0;
    static char ch=getchar();
    while(ch<'0'||ch>'9')   ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int n,m,need,ans;
int l,r,father[N];
inline int getfather(int x)
{
    if(father[x]==x)    return x;
    father[x]=getfather(father[x]);
    return father[x];
}
inline bool cmp(const Edge &x,const Edge &y)
{
    if(x.val==y.val)    return x.color<y.color;
    return x.val<y.val;
}
inline bool check(int del)
{
    for(int i=1;i<=m;i++)   if(edge[i].color==0)    edge[i].val+=del;
    for(int i=1;i<=n;i++)   father[i]=i;
    sort(edge+1,edge+m+1,cmp);
    int white=0,sum=0,cnt=0,flag;
    for(int i=1;i<=m;i++)
    {
        int fx=getfather(edge[i].from),fy=getfather(edge[i].to);
        if(fx!=fy)
        {
            father[fx]=fy;  sum+=edge[i].val; cnt++;
            if(edge[i].color==0)    white++;
            if(cnt==n-1)
            {
                if(white>=need) ans=sum-del*need,flag=1;
                else flag=0;
                break;
            }
        }
    }
    for(int i=1;i<=m;i++)   if(edge[i].color==0)    edge[i].val-=del;
    return flag;
}
int main()
{
    read(n); read(m); read(need);
    for(int i=1;i<=m;i++)
    {
        read(edge[i].from); read(edge[i].to); edge[i].from++; edge[i].to++;
        read(edge[i].val);  read(edge[i].color);
        r=max(r,edge[i].val+1);
    }
    l=-r;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid;
    }
    cout<<ans;
    return 0;
}

转载于:https://www.cnblogs.com/Patrickpwq/articles/9848734.html