洛谷2619 [国家集训队2012]Tree I

题意

有一个无向带权连通图，每条边是黑色或白色。求一棵最小权的恰好有 $need$ 条白色边的生成树。保证有解。

题解

我最开始想的是直接先对白边跑有 $need$ 条边的最小生成树，再对黑边跑剩下的就行了。但打到一半突然发现不行，于是便跑去看题解。

显然直接跑最小生成树白边就很可能多或者少。如果多了就说明白边的权值大多比较小，那么我们就可以给所有白边加一个权值 $x$ 然后再跑；如果白边少了同理。

很显然这个是满足单调的，所以我们可以对 $x$ 进行二分，答案就是跑出来的树的权值减去 $x\times need$ 。

upd:20190511

wzx大佬提出，将 sum>=need 改成 sum==need 时只能得 $35$ ，于是我们对这个问题深入探讨了下。

因为排序时贪心的策略是同权时选白边，所以同权时就会出现白边比 $need$ 多的情况，所以相等时更新答案显然是不行的。

而题目保证有解，这就意味着最后一次 $sum>need$ 一定是同权的情况，所以这么写没有问题。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int st,ed,w,col;
} edge[100005];
int n,m,need,ans,fa[100005];

inline bool cmp(Edge x,Edge y) { return (x.w==y.w) ? x.col<y.col : x.w<y.w; }

inline void init() { for (int i=1;i<=n;i++) fa[i]=i; }

int getfa(int x) { return (x==fa[x]) ? x : fa[x]=getfa(fa[x]); }

inline bool merge(int x,int y)
{
    int gfx=getfa(x),gfy=getfa(y);
    if (gfx==gfy) return 0;
    fa[gfx]=gfy;
    return 1;
}

inline int check(int x)
{
    int sum=0,cnt=0,ans=0;
    for (int i=1;i<=m;i++) edge[i].w+=(edge[i].col^1)*x;
    sort(edge+1,edge+m+1,cmp);
    init();
    for (int i=1;i<=m;i++)
    {
        int x=edge[i].st,y=edge[i].ed;
        if (!merge(x,y)) continue;
        ans+=edge[i].w;
        sum+=edge[i].col^1;
        cnt++;
        if (cnt==n-1) break;
    }
    for (int i=1;i<=m;i++) edge[i].w-=(edge[i].col^1)*x;
    return (sum>=need)*ans;
}

int main()
{
    n=read(); m=read(); need=read();
    for (int i=1;i<=m;i++) edge[i].st=read()+1,edge[i].ed=read()+1,edge[i].w=read(),edge[i].col=read();
    int l=-100,r=100,ans=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (int now=check(mid)) l=mid+1,ans=now-mid*need;
        else r=mid-1;
    }
    printf("%d",ans);
    return 0;
}