[BZOJ 1196][HNOI 2006]公路修建问题

?

可以说这是个瓶颈生成树的题？

不算很难的图论题，构思非常巧妙。。。

二分生成树的最大边权x，判断这样的生成树是否存在就行了。。。

每次判断时分成两步走，首先要限制c1小于等于x，判断生成树中的树边个数是否小于等于k，若大于k，表明这个生成树不存在。

再限制c2小于等于x，由于c2

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define MAXE 20050 #define MAXV 10050 using namespace std; struct edge { int u,v,c1,c2; }edges[MAXE]; int n,m,K; int f[MAXV]; int findSet(int x) { if(f[x]==x) return x; return f[x]=findSet(f[x]); } bool judge(int x) //设生成树最大的边权为x，判断这样的生成树是否存在 { for(int i=1;i<=n;i++) f[i]=i; int cnt=0; //当前生成树中树边总数 for(int i=1;i<=m;i++) //存在生成树中c1最大值小于等于x的限制，但是办不到，这样的生成树不存在 { if(edges[i].c1>x) continue; int rootu=findSet(edges[i].u),rootv=findSet(edges[i].v); if(rootu!=rootv) { f[rootu]=rootv; cnt++; } } if(cnt
       
        x) continue; int rootu=findSet(edges[i].u),rootv=findSet(edges[i].v); if(rootu!=rootv) { f[rootu]=rootv; cnt++; } } if(cnt
        
         
?
         
?
         
?
 ??