D题
D-旅游_牛客小白月赛69（重现赛）@PHarr (nowcoder.com)
题意：自己看
题解：最小生成树模板题
最小生成树算法（这个就是给你一个图里面修路让城市和城市之间想联通，每一条路都是有一个修路的花费，最小生成树就是全部的点联通最小的代价）
现在怎么处理
首先我们排序每一个连接的边的代价进行从小到大排序
然后开始枚举如果再两个点不在一个树里面，那么我们就需要加上这个边的代价，然后把这点连到树里面（这里我们用并查集进行处理，find函数找父节点加边）
然后你就会得到这个情况下的最小的代价
这题我们需要二分政府给的花费，带入最小生成树里面判断结果即可
#include <bits/stdc++.h> //#pragma GCC optimize("Ofast") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> //#define double long double #define int long long //#define endl '\n'; using namespace std; const int N=3e6+7,M=1e1; const int INF = 0x3f3f3f3f; const int mod=100003; int kmp(int a,int k,int p) { int ans=1; while (k) { if(k&1) ans=ans*a%p; k>>=1; a=a*a%p; } return ans; } typedef pair<int,int> PII; int fu[N]; int ch[N]; int n,m,c; struct G{ int x,y,val; }a[N]; int find(int x) { if (fu[x] == x) return x; else return fu[x] = find(fu[x]); } bool cmp(G x,G y) { return x.val<y.val; } bool kruskal(int x) { for(int i=1;i<=n;i++) { fu[i]=i; } int ans=0; int k=0; for(int i=1;i<=m;i++) { int x1=a[i].x,y1=a[i].y,c1=a[i].val; x1=find(x1),y1=find(y1); if(x1!=y1) { fu[x1]=y1; if(c1>x) { ch[++k]=c1; } } } for(int i=k;i>=1;i--) { ans+=(k+1-i)*ch[i]; } return ans<=c; } void solve() { cin>>n>>m>>c; for(int i=1;i<=m;i++) { int x,y,val; cin>>x>>y>>val; a[i]={x,y,val}; } sort(a+1,a+1+m,cmp); int l=0,r=1e9; while (l<r) { int mid=(l+r)/2; if(kruskal(mid)) r=mid; else l=mid+1; } cout<<l<<endl; } signed main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int T=1; // cin>>T; while(T--){ solve(); } return 0; }