[bzoj2654] tree

2654: tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 3723 Solved: 1596
[Submit][Status][Discuss]

Description

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

题目保证有解。

Input

第一行V,E,need分别表示点数，边数和需要的白色边数。

接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。

V<=50000,E<=100000,所有数据边权为[1,100]中的正整数。

Sample Input

2 2 1
0 1 1 1
0 1 2 0

Sample Output

HINT

原数据出错，现已更新 by liutian,但未重测---2016.6.24

题意：

够简洁的吧……

题解：

只要我们能够手动控制最小生成树$T$中白边的条数$x$，那么这题就完事了。

那么我们考虑如何控制白边条数呢？

显然给每条白边权值都加一个正数$x$，最小生成树中白边的数量一定不增。

那么随着$x$的增加，白边的数量$y$单调递减或不变。

所以我们二分就可以找到最后一个$白边数量leq need$的位置$x$和第一个$白边数量geq need$的位置$y$。

显然这两种状态的加数是相邻的。那么如果他们中有一个白边数量等于$need$则直接输出权值即可。

如果白边数量均不等于$need$，那么显然有很多权值相同的黑边替换掉了很多权值相同的白边。

我们在统计答案时将这些黑边替换成白边即可。

若有兴趣了解该题解的严格证明请移步这里。

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
#define MAXN 100005
#define MAXM 500005
#define INF 0x7fffffff
#define ll long long

struct edge{
    ll u,v,w,c;
    bool operator<(const edge b)const {
        return w==b.w?c<b.c:w<b.w;
    }
}e[MAXM];
ll N,M,K,sum,f[MAXN];
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
        if(c=='-')
            f=-1;
    for(;isdigit(c);c=getchar())
        x=x*10+c-'0';
    return x*f;
}

inline ll find(ll x){return f[x]==x?x:f[x]=find(f[x]);}
inline ll check(ll x){
    for(ll i=1;i<=N;i++) f[i]=i;
    for(ll i=1;i<=M;i++)
        if(e[i].c==0) 
            e[i].w+=x;
    sort(e+1,e+1+M);
    ll cnt=0;sum=0;
    for(ll i=1;i<=M;i++){
        ll t1=find(e[i].u),t2=find(e[i].v);
        if(t1!=t2){
            f[t2]=t1,sum+=e[i].w;
            if(e[i].c==0) cnt++;
        }
    }
    for(ll i=1;i<=M;i++)
        if(e[i].c==0)
            e[i].w-=x;
    return cnt;
}

int main(){
    //freopen("tree7.in","r",stdin);
    //freopen("tree.out","w",stdout);
    N=read(),M=read(),K=read();
    ll ans=0,ws=0;
    for(ll i=1;i<=M;i++){
        e[i].u=read()+1,e[i].v=read()+1;
        e[i].w=read(),e[i].c=read();
        if(e[i].c==0) ws++;
    }
    ll l=0,r=1000;
    while(l<=r){
        ll mid=(l+r)>>1;
        //cout<<mid<<" "<<check(mid)<<endl;
        if(check(mid)<K) r=mid-1;
        else l=mid+1; 
    }
    int num=check(l-1);
    printf("%lld
",sum-K*(l-1));
    return 0;
}