【题目链接】 

 

【题目大意】

　　对于每条可能维修的公路可选择修一级公路或者二级公路，价值不同

　　要求图连通，且至少有k条一级公路时最大价值公路价值最小。

 

【题解】

　　二分答案，从一级公路开始处理，利用并查集验证两个条件。

 

【代码】

#include 
     
      #include 
      
       using namespace std;const int N=20005;int f[10005],x[N],y[N],c1[N],c2[N],l=1,r=0,ans,n,m,k;int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}bool check(int u){    int k1=0,k2=0;    for(int i=1;i<=n;i++)f[i]=i;    for(int i=1;i
       
        u)continue;        int fx=sf(x[i]),fy=sf(y[i]);        if(fx!=fy){            f[fy]=fx;            k1++;        }    }    for(int i=1;i
        
         u)continue;        int fx=sf(x[i]),fy=sf(y[i]);        if(fx!=fy){            f[fy]=fx;            k2++;        }    }return (k1>=k&&k1+k2==n-1);}int main(){    scanf("%d%d%d",&n,&k,&m);    for(int i=1;i
         
          >1;        if(check(mid))r=mid-1,ans=mid;        else l=mid+1;    }printf("%d\n",ans);    return 0;}