题意：

修n-1条公路将n个点连通，每个点可建一级公路也可建二级公路，要求一级公路必须有k条，要求花费最多的公路花费最少。

题解：

首先二分最大花费，接着判定：先在不产生环的前提下（用并查集维护）让每条路尽量修一级公路，如果最后无法构成树则考虑修二级公路。

代码：

1 #include 
     
        2 #include 
      
        3 #include 
       
         4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define maxn 10500 6 using namespace std; 7  8 int n,k,m,u[maxn*2],v[maxn*2],c1[maxn*2],c2[maxn*2],mx,fa[maxn],cnt; 9 int find(int x){
   return x==fa[x]?x:fa[x]=find(fa[x]);}10 bool check(int lim){11     inc(i,1,n)fa[i]=i; cnt=0;12     inc(i,1,m)if(c1[i]<=lim){13         int x=find(u[i]),y=find(v[i]); if(x==y)continue; fa[y]=x; cnt++;14     }15     if(cnt
        
         >1;27         if(check(mid))ans=mid,r=mid-1;else l=mid+1;28     }29     printf("%d",ans); return 0;30 }
        
       
      
     

20160531