这道题我们可以贪心，首先按建一级公路的花费从小到大排序，然后用最小生成树的做法选出K条并做好标记，然后再按建一级公路和建二级公路的花费的最小值排序，再做一遍最小生成树，更新答案。这样做的正确性是因为先加入了有用的K条一级公路，并且满足这些公路最大值最小，然后又按照最小生成树的方法加边，又满足后加入的边的最大值最小，因此整个过程都满足最大值最小
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 200000 struct edge { int fr,to,cost1,cost2,ord; }e[maxn]; int n,m,k,father[maxn],cnt,ans; bool flag[maxn]; bool cmp(edge a,edge b) { return a.cost1<b.cost1; } bool cmp1(edge a,edge b) { return min(a.cost1,a.cost2)<min(b.cost1,b.cost2); } int getfather(int x) { if (x!=father[x]) father[x]=getfather(father[x]); return father[x]; } int main() { scanf("%d%d%d",&n,&k,&m); for (int i=1;i<m;i++) { scanf("%d%d%d%d",&e[i].fr,&e[i].to,&e[i].cost1,&e[i].cost2); e[i].ord=i; } sort(e+1,e+m,cmp); for (int i=1;i<=n;i++) father[i]=i; for (int i=1;i<m;i++) { int x=e[i].fr; int y=e[i].to; x=getfather(x); y=getfather(y); if (x==y) continue; // printf("%d %d\n",e[i].fr,e[i].to); cnt++; flag[e[i].ord]=1; father[y]=x; ans=max(ans,e[i].cost1); if (cnt==k) break; } sort(e+1,e+m,cmp1); for (int i=1;i<m;i++) { if (flag[e[i].ord]) continue; int x=e[i].fr; int y=e[i].to; x=getfather(x); y=getfather(y); if (x==y) continue; //printf("%d %d\n",e[i].fr,e[i].to); cnt++; father[y]=x; ans=max(ans,min(e[i].cost1,e[i].cost2)); if (cnt==n-1) break; } printf("%d\n",ans); return 0; }