竟然一遍A了湖南省选题、感人至深
这个题一看便知是要二分的。
所以剩下的就是利用构造树来检验
首先，对于c1，我们可以求一颗最小生成树，来保留尽可能多的边（因为大于检验值的都不合法，需要删掉，为了让保留的边尽可能多，就需要最小生成树）
但对于c1，一定有小于二分值的，那他会不会贡献答案呢？
如图，不会。
然后剩下的c1便一定都不会再被选了，可以判断一下边数是否大于k来检验
如果大于k，则继续从c2里面选边，选到边权>二分值为止，看一下边数就可以了
O（nlog^2n）级别，跑得飞快
码：
#include<iostream> #include<cstdio> #include<algorithm>; #define N 40004 using namespace std; int fu[N],i,m,n,a,b,c1,c2,k,maxx,l,r,ans; int find(int x) { if(fu[x]!=x)fu[x]=find(fu[x]); return fu[x]; } struct bian { int q,z,c,cc; }bb[N],dd[N]; bool cmp(bian a,bian b) { return a.c<b.c; } bool cmp2(bian a,bian b) { return a.cc<b.cc; } int main() { scanf("%d%d%d",&n,&k,&m); for(i=1;i<m;i++) { scanf("%d%d%d%d",&a,&b,&c1,&c2); bb[i].q=a; bb[i].z=b; bb[i].c=c1; bb[i].cc=c2; dd[i]=bb[i]; maxx=max(maxx,max(c1,c2)); } sort(bb+1,bb+m,cmp); sort(dd+1,dd+m,cmp2); l=1;r=maxx; while(l<r) { int mid=(l+r)>>1; for(i=1;i<=n;i++)fu[i]=i; int o=0; for(i=1;i<m;i++) { if(bb[i].c>mid||o==n-1)break; int f1=find(bb[i].q),f2=find(bb[i].z); if(f1!=f2) { fu[f1]=f2; ++o; } } if(o<k) { l=mid+1; continue; } for(i=1;i<m;i++) { if(dd[i].cc>mid||o==n-1)break; int f1=find(dd[i].q),f2=find(dd[i].z); if(f1!=f2) { fu[f1]=f2; ++o; } } if(o==n-1) { ans=mid; r=mid; }else { l=mid+1; } } printf("%d",ans); }
