Solution

二分答案+并查集.

由于考虑到是要求花费的最小值,直接考虑到二分.

然后对于每一个二分出来的答案,模拟 \(Kruskal\) 的过程再做一遍连边.

同时用并查集维护联通块信息.

最后看连的边数以及\(1\)边是否满足要求即可.

Code

#include
    
     using namespace std;const int maxn=20008;int n,k,m,v[maxn];struct sj{int x,y,w1,w2,id;}a[maxn];int fa[maxn],ans,pd[maxn];int find(int x)    {if(fa[x]==x)return x;else return fa[x]=find(fa[x]);}void join(int x,int y)    {x=find(x),y=find(y);if(x!=y)fa[x]=y;}bool cmp(sj x,sj y){return x.w1
     
      '9'){if(ch=='-')f=-1;ch=getchar();}    while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();}    return f*w;}bool jud(int x){    for(int i=1;i<=n;i++)fa[i]=i;int cnt=0,js=0;    memset(v,0,sizeof(v));    sort(a+1,a+m,cmp);    for(int i=1;i