这道题在显然是最小生成树，但是很显然我是不会打最小生成树的。
题意描述
给定一张 \(n\) 个点 \(m\) 条边的无向图，求出无向图的一棵最小生成树，满足一号节点的度数不超过给定的整数 \(s\)。
具体思路
首先，看到这种度数最多为 \(s\) 的题，显然想到 wqs 二分。但是 wqs 二分是恰好选 \(s\) 条边是最优，因此考虑证明这一性质。
设平面直角坐标系上的点 \((x,f(x))\)，其中 \(x\) 代表选多少条边，\(f(x)\) 代表选 \(x\) 条边时的边权之和。
设当前 \(f(x)\) 最优的情况是选 \(s\) 条边连着 \(1\) 号节点，即此时的生成树边权之和最小。
-
若我们选多一条边连着 \(1\) 号节点，那么就会多加一条边的权值，显然权值之和没有选 \(s\) 条边优。
-
若我们选少一条边连着 \(1\) 号节点，那么就会导致有的点要连到其它节点上来保证连通性。由于我们选 \(s\) 条边的时候是最优的，因此我们现在选的点要连到更大的边上，因此权值之和没有选 \(s\) 条边优。
因此 \(f(x)\) 具有凸函数性质，即斜率具有单调性，故可以二分。
Code
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1100;
unordered_map<string,int>Hash;
int n,m,k,s,fa[N];
struct node{int x,y,c;}a[N];
bool cmp(node n1,node n2){
if(n1.c+k*(n1.x==1)==n2.c+k*(n2.x==1))return n1.x!=1;
return n1.c+k*(n1.x==1)<n2.c+k*(n2.x==1);
}
int get(int x){
if(fa[x]==x)return x;
return fa[x]=get(fa[x]);
}
PII kruskal(){
int ans=0,cnt=0;
for(int i=1;i<=n;i++)fa[i]=i;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
int x=a[i].x,y=a[i].y,c=a[i].c;
int tx=get(x),ty=get(y);
if(tx!=ty){
fa[tx]=ty;
ans=ans+c;
if(x==1){
cnt++;
ans=ans+k;
}
}
}
return {cnt,ans};
}
int solve(){
int l=0,r=1000;
while(l<=r){
int mid=(l+r)>>1;k=mid;
if(kruskal().first>s)l=mid+1;
else r=mid-1;
}
return l;
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d",&m);
Hash.clear();n=0;
Hash["Park"]=++n;
for(int i=1;i<=m;i++){
string x,y;int c;
cin>>x>>y>>c;
if(!Hash[x])Hash[x]=++n;
if(!Hash[y])Hash[y]=++n;
a[i]=node{Hash[x],Hash[y],c};
if(a[i].x>a[i].y)swap(a[i].x,a[i].y);
}
scanf("%d",&s);
printf("Total miles driven: ");
k=0;
if(kruskal().first>s)k=solve();
printf("%d\n",kruskal().second-k*s);
if(t)puts("");
}
return 0;
}