bzoj2654 tree

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

正解：二分+$kruskal$。

简直是一道神题啊。。

如果直接$kruskal$求最小生成树，是无法保证白边数量的，那么我们考虑如果改变白边的数量。我们可以把白边全部都加上一个权值，也就是我们二分的值，然后跑最小生成树，同时记录白边数量。当白边数量$>=need$时，$l=mid+1$，否则$r=mid-1$，更新答案就是这棵生成树的权值和减去所有白边的增量。

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstring>
 5 #include <cstdlib>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <queue>
10 #include <stack>
11 #include <map>
12 #include <set>
13 #define inf (1<<30)
14 #define N (200010)
15 #define il inline
16 #define RG register
17 #define ll long long
18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
19 
20 using namespace std;
21 
22 struct edge{ int u,v,w,c; }g[N];
23 
24 int fa[N],n,m,ans,need;
25 
26 il int gi(){
27     RG int x=0,q=1; RG char ch=getchar();
28     while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
29     if (ch=='-') q=-1,ch=getchar();
30     while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
31     return q*x;
32 }
33 
34 il int cmp(const edge &a,const edge &b){
35     if (a.w==b.w) return a.c<b.c; return a.w<b.w;
36 }
37 
38 il int find(RG int x){ return fa[x]==x ? x : fa[x]=find(fa[x]); }
39 
40 il int check(RG int key){
41     for (RG int i=1;i<=m;++i) if (!g[i].c) g[i].w+=key;
42     sort(g+1,g+m+1,cmp); RG int tt=0,sum=0;
43     for (RG int i=1;i<=n;++i) fa[i]=i;
44     for (RG int i=1,x,y,k=0;i<=m;++i){
45     x=find(g[i].u),y=find(g[i].v);
46     if (x!=y) ++k,fa[x]=y,tt+=g[i].c^1,sum+=g[i].w;
47     if (k==n-1) break;
48     }
49     if (tt>=need) ans=sum-tt*key;
50     for (RG int i=1;i<=m;++i) if (!g[i].c) g[i].w-=key;
51     return tt>=need;
52 }
53 
54 il void find(){
55     RG int l=-100,r=100,mid;
56     while (l<=r){
57     mid=(l+r)>>1;
58     if (check(mid)) l=mid+1; else r=mid-1;
59     }
60     return;
61 }
62 
63 il void work(){
64     n=gi(),m=gi(),need=gi();
65     for (RG int i=1;i<=m;++i)
66     g[i].u=gi()+1,g[i].v=gi()+1,g[i].w=gi(),g[i].c=gi();
67     find(); printf("%d
",ans); return;
68 }
69 
70 int main(){
71     File("tree");
72     work();
73     return 0;
74 }