题目传送门(BZOJ)
>原文链接<

题解 :

最大权最小,明显的二分答案特征

考虑二分答案,对于权值小于mid的边,优先满足一级公路。若不足K条则把 l 变大, 若足够则连接二级公路。

由于题目要求必须是 n-1 条边,所以这样一定是正确的。

代码 :

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int N = 11000;const int M = 22000;int l,r;int n,m,k;int fa[N];struct node { int s,t,v1,v2;}e[M];bool cmp(const node &a, const node &b) { if(a.v1==b.v1)return a.v2<b.v2; else return a.v1<b.v1;}void init() { scanf("%d%d%d",&n,&k,&m); for (int i=1;i<m;i++) { scanf("%d%d%d%d",&e[i].s,&e[i].t,&e[i].v1,&e[i].v2); if(e[i].v1>r)r=e[i].v1; } sort(e+1,e+m,cmp);}int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]);}bool check(int x) { for(int i=1;i<=n;i++) { fa[i]=i; } int cnt=0; for(int i=1;i<=m;i++) { if(e[i].v1>x)continue; int dx=find(e[i].s),dy=find(e[i].t); if(dx!=dy) { fa[dx]=dy; cnt++; } } if(cnt<k)return 0; for(int i=1;i<=m;i++) { if(e[i].v2>x)continue; int dx=find(e[i].s),dy=find(e[i].t); if(dx!=dy) { fa[dx]=dy; cnt++; } } if(cnt!=n-1)return 0; return 1;}int main() { init(); int ans; while(l<=r) { int mid = (l+r) >>1; if(check(mid)) { ans=mid; r = mid-1 ; } else { l = mid +1 ; } } printf("%d\n",ans);}