[国家集训队2012]tree(陈立杰)

题意

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

题目保证有解。

solution

直接kruskal得到的最小生成树的白边可能会有小于或大于need的情况

但是我们发现一个性质:

白边的权值越大，最小生成树中的白边一定越少，相反，一定越多 (其实，从权值的特殊范围也可以想出)

所以我们可以给所有白边加上一个权值，使其最小生成树满足need条白边

而这个值我们可以二分求出

(排序要按照权值第一关键字颜色第二关键字尽量把白边放在前面)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define mem(a,b) memset(a,b,sizeof(a))
 6 using namespace std;
 7 const int N=100006;
 8 
 9 struct son
10 {
11     int u,v,w,co;
12     friend bool operator < (son a,son b)
13     {
14         return a.w==b.w?a.co>b.co:a.w<b.w;
15     }
16     /*friend bool operator < (son a,son b)
17     {
18         return a.w<b.w;
19     }*/
20 };
21 son ji[N],temp[N];
22 int n,m,ne;
23 int u,o,p,l;
24 int ans,vnow,com;
25 
26 int fa[N];
27 int fin(int x)
28 {
29     if(fa[x]==-1)
30       return x;
31     fa[x]=fin(fa[x]);
32     return fa[x];
33 }
34 
35 int check()
36 {
37     mem(fa,-1);
38     vnow=0;
39     int now=0,num=0;
40     for(int i=1;i<=m;++i)
41     {
42         temp[i].u=ji[i].u;
43         temp[i].v=ji[i].v;
44         temp[i].w=ji[i].w+ji[i].co*com;
45         temp[i].co=ji[i].co;
46     }
47     sort(temp+1,temp+1+m);
48     for(int i=1;i<=m;++i)
49     {
50         int x=fin(temp[i].u),y=fin(temp[i].v);
51         if(x!=y)
52         {
53             fa[x]=y;
54             ++now;
55             num+=temp[i].co;
56             vnow+=temp[i].w;
57         }
58         if(now==n-1)
59           break;
60     }
61     return num;
62 }
63 
64 int main(){
65     
66     //freopen("nt2012_tree.in","r",stdin);
67 //    freopen("nt2012_tree.out","w",stdout);
68     
69     scanf("%d%d%d",&n,&m,&ne);
70     for(int i=1;i<=m;++i)
71     {
72         scanf("%d%d%d%d",&ji[i].u,&ji[i].v,&ji[i].w,&ji[i].co);
73         ji[i].co^=1;
74         ++ji[i].u;
75         ++ji[i].v;
76     }
77     
78     int ans=0;
79     int l=-106,r=106;
80     while(l<=r)
81     {
82         int mid=(l+r)>>1;
83         com=mid;
84         if(check()>=ne){ans=vnow-ne*com;l=mid+1;}
85         else r=mid-1;
86     }
87     
88     cout<<ans;
89     //while(1);
90     return 0;
91 }

code

[国家集训队2012]tree(陈立杰)

相关推荐