[bzoj2654] tree

Description

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

Input

第一行(V) ,(E) ,(need) 分别表示点数，边数和需要的白色边数。
接下来 (E) 行,每行 (s),(t),(c),(col) 表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。

Output

一行表示所求生成树的边权和。
(V leq 50000) , (Eleq 100000) ,所有数据边权为 ([1,100]) 中的正整数。

Sample Input

2 2 1

0 1 1 1

0 1 2 0

Sample Output

2

---

题解

对本蒟蒻来说这是一道做法很新奇很高级的题……

感性理解，如果给所有白边都加上一个正值 (mid) ，再跑最小生成树，其中的白边数目会减少（(vice) (versa)）
那么可以二分给所有白边加的值 (mid) ，跑 (kruskal) ，直到白边数目为 (need) ，用此时最小生成树值 (-mid imes need) 就是最终答案

还有一些小细节（下面是从大神博客中引用来的）

但是你可能怀疑二分的正确性？即如果给白色边边权加上 (mid)，则所选白色边 (>need)，如果加上 (mid+1)，则所选白色边 (<need) 。这种情况看似没法处理。但是考虑一下克鲁斯卡尔的加边顺序。可以发现如果出现这种情况，一定是有很多相等的白边和黑边。因为数据保证合法。所以我们可以把一些白边替换成黑边。所以我们要在白边数 (leq need)的时候跟新答案。

---

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
const int N = 50005;
 
struct node{
    int v,len,col;
    node *nxt;
}pool[N*4],*h[N],*ed[N*4];
int cnt;
void addedge(int u,int v,int len,int col){
    node *p=&pool[++cnt],*q=&pool[++cnt];
    p->v=v;p->nxt=h[u];h[u]=p; p->len=len;p->col=col;
    q->v=u;q->nxt=h[v];h[v]=q; q->len=len;q->col=col;
}
int tot;
 
int n,m,need;
int w[205];
 
struct data{
    int v,len,col;
    data(int v=0,int len=0,int col=0): v(v),len(len),col(col) {}
    bool operator < (const data &b) const { return len>b.len; }
};
priority_queue<data> que;
int d[N];
int prim(int x){
    int u,v,c,ret=0;
    for(int i=0;i<n;i++) d[i]=1e8;
    que.push(data(0,d[0],1));
    while(!que.empty()){
        u=que.top().v; c=que.top().col;
        que.pop();
        if(!d[u]) continue;
        ret+=1-c; w[x]+=d[u]; d[u]=0;
        for(node *p=h[u];p;p=p->nxt)
            if(d[v=p->v]!=0 && d[v]>p->len){
                d[v]=p->len;
                que.push(data(v,d[v],p->col));
            }
    }
    w[x]-=1e8;
    return ret;
}
int check(int x){
    for(int i=0;i<tot;i++) ed[i]->len+=x;
    int ret=prim(x+100);
    w[x+100]-=ret*x;
    for(int i=0;i<tot;i++) ed[i]->len-=x;
    return ret;
}
 
int main()
{
    int x,y,z,c;
    scanf("%d%d%d",&n,&m,&need);
    for(int i=0;i<m;i++){
        scanf("%d%d%d%d",&x,&y,&z,&c);
        addedge(x,y,z,c);
        if(c==0) ed[tot++]=&pool[cnt],ed[tot++]=&pool[cnt-1];
    }
     
    int l=-100,r=100,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(check(mid)<need) r=mid-1;
        else l=mid;
    }
    printf("%d
",w[l+100]);
     
    return 0;
}