bzoj 2654 tree 二分+kruskal

tree

Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 2739 Solved: 1126
[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

题解：get了一种新的套路，可以二分一个值，让白边都减去这个值，然后排序后，可以发现这样具有二分性

　　　然后可以瞎搞，不过注意权值相等的问题，所以每次需要加的是二分值的的贡献。

 1 #include<cstring>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<queue>
 7 
 8 #define N 50007
 9 #define M 100007
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;char ch=getchar();
14     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
15     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
16     return x*f;
17 }
18 
19 int n,m,ned;
20 int ans,num;
21 int fa[N];
22 struct Node
23 {
24     int x,y,w,c;
25     friend bool operator<(Node x,Node y)
26     {
27         if (x.w==y.w) return x.c<y.c;
28         return x.w<y.w;
29     }
30 }a[M],e[M];
31 
32 int find(int num)
33 {
34     if (fa[num]!=num) fa[num]=find(fa[num]);
35     return fa[num];
36 }
37 bool judge(int zhi)
38 {
39     ans=0,num=0;
40     for (int i=1;i<=m;i++)
41     {
42         e[i]=a[i];
43         if (!a[i].c) e[i].w+=zhi;
44     }
45     sort(e+1,e+m+1);
46     for (int i=1;i<=n;i++) fa[i]=i;
47     for (int i=1;i<=m;i++)
48     {
49         int u=find(e[i].x),v=find(e[i].y);
50         if (u!=v)
51         {
52             fa[v]=u;
53             if (!e[i].c) num++;
54             ans+=e[i].w;
55         }
56     }
57     ans-=zhi*num;
58     if (num>=ned) return true;
59     else return false;
60 }
61 int main()
62 {
63     n=read(),m=read(),ned=read();
64     for (int i=1;i<=m;i++)
65         a[i].x=read()+1,a[i].y=read()+1,a[i].w=read(),a[i].c=read();
66     
67     int l=-105,r=105;
68     while(l<r)
69     {
70         int mid=(l+r+1)>>1;
71         if (judge(mid)) l=mid;
72         else r=mid-1;
73     }
74     printf("%d
",ans);
75 }