hdu 4253 Two Famous Companies BZOJ 2654 tree

【题意】：给出n个点，m条边，边分为两种，一种是A公司的，一种是B公司的。边上有权值，问用n-1条边把n个点连起来的最小费用是多少，其中A公司的边刚好有k条。题目保证有解。

思路：我们发现，如果我们给白边增加权值，做最小生成树，由于白边权值增大，导致不容易选白边。记f(x)为给白边增加x权值，做最小生成树后，选白边的数量，可以发现，f(x)随x增大而减小。所以可以二分x

首先，直接做MST的话白色边的数量是无法估计的。可能比要求的多，也可能更少

所以考虑怎样调整白色边的数量

通过这个思路，可以想到如果把所有白色边的权值加上/减去一个Δ，那么不考虑答案正确性，可以保证这时候MST跑出来之后白色边的数量一定会增加/减少

那么我们就可以直接二分一个值，使得白边的数量符合要求。

事实上可以证明当我们限定白边的数量一定的时候，MST的答案也是唯一的

那么我们在白边上加上Δ之后算出来MST的答案会多出need*Δ，直接减掉就好了

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 struct node

 {

     int v1,v2;

     int w;

 } s[],t[];

 int n,m,k,cnts,cntt;

 int father[],sum;

 int cmp(const node a,const node b)

 {

    return a.w<b.w;

 }

 int find(int x)

 {

     int i=x,root;

     while(x!=father[x])

         x=father[x];

     root=x;

     x=i;

     while(x!=father[x])

     {

         i=father[x];

         father[x]=root;

         x=i;

     }

     return root;

 }

 int deal(int x)

 {

     for(int i=; i<=n; i++)

         father[i]=i;

     int lens=,lent=,pp=;

     sum=;

     while(lens<cnts||lent<cntt)

     {

         if(s[lens].w+x<=t[lent].w)

         {

             int s1=find(s[lens].v1);

             int s2=find(s[lens].v2);

             if(s1!=s2)

             {

                 father[s1]=s2;

                 sum+=s[lens].w+x;

                 pp++;

             }

             lens++;

         }

         else

         {

             int s1=find(t[lent].v1);

             int s2=find(t[lent].v2);

             if(s1!=s2)

             {

                 father[s1]=s2;

                 sum+=t[lent].w;

             }

             lent++;

         }

     }

     if(pp>=k)   return ;

     else    return ;

 }

 int main()

 {

     int text=;

     while(scanf("%d%d%d",&n,&m,&k)>)

     {

         cnts=,cntt=;

         for(int i=; i<m; i++)

         {

             int v1,v2,w,tmp;

             scanf("%d%d%d%d",&v1,&v2,&w,&tmp);

             if(tmp==)

             {

                 s[cnts].v1=v1;

                 s[cnts].v2=v2;

                 s[cnts].w=w;

                 cnts++;

             }

             if(tmp==)

             {

                 t[cntt].v1=v1;

                 t[cntt].v2=v2;

                 t[cntt].w=w;

                 cntt++;

             }

         }

         sort(s,s+cnts,cmp);

         sort(t,t+cntt,cmp);

         t[cntt].w=s[cnts].w=(<<);

         printf("Case %d: ",++text);

         int l=-,r=;

         int ans=;

         while(l<=r)

         {

             //sum=0;

             int mid=(l+r)/;

             if(deal(mid))

             {

                 l=mid+;

                 ans=sum-mid*k;

             }

             else r=mid-;

         }

         printf("%d\n",ans);

     }

     return ;

 }