题意
求 $N$ 点无向图的最小生成树，满足 $1$ 号节点度数 $\le s$ 。$N\le 30$ 。
题解
思想
考虑构造一个以 $1$ 号节点为根的树，则 $1$ 号节点必须与子树中所有连通块相连。记录去掉 $1$ 号节点后的连通块个数，即 $1$ 号节点的最小度数，为 $tcnt$ 。（题目保证有解即 $tcnt\le s$）
对每个连通块分别求出最小生成树，这样就得到了除 $1$ 号节点外的局部最优解，同时全局最优解只与 $1$ 号结点的连法有关。
先考虑度数为 $tcnt$ 的最优解，显然从每个连通块选择离 $1$ 最近的节点与之相连最优。
继续考虑度数为 $[tcnt+1,s]$ 时的最优解，可以用换边来解决。
用不在树上的边 $(1,x)$ 替换 $(u,v)$ ，其中 $(u,v)$ 是原树中 $1\rightarrow x$ 路径上的一条边，贪心找权值最大的 $(u,v)$ 替换掉是最优的。
枚举所有 $(1,x)$ 并得到 $(u,v)$ ，设两边的权值为 $z$ 和 $w$ ，显然找到 $w-z$ 最大的 $x_0$ 最优，这样答案就减少了 $w_0-z_0$ 。
这样的换边最多可以做 $s-(tcnt+1)+1=s-tcnt$ 次，不过当 $w_0-z_0\le 0$ 时就可以不用再做了。
实现
- 用
map建立人名和编号的映射，并建边。 dfs1()划分连通块，并用v记录连通块内的所有边，每次搜索完后用kruskal()求最小生成树。- 用
v记录与 $1$ 号节点相连的所有边，同样做一次kruskal()。（即从每个连通块选择离 $1$ 最近的节点与之相连，因为连通块都已经用并查集合并了起来，所以这样做是等价的） - 进行 $s-tcnt$ 次换边操作，枚举 $(1,x)$ 并得到边权最大的 $(u,v)$ 记录为
e。在外层用mx保存 $w-z$ 的最大值，同时更新e0表示最大时的 $(u,v)$ ，x0为最大时的 $(1,x)$ 。最后用x0替换e0即可。如果 $mx\le 0$ 就退出循环。
代码
#include<bits/stdc++.h>
using namespace std;
struct Edge {
int next,from,to,w;
} edge[1805];
string a,b;
vector <int> v;
map <string,int> mp;
int t,n,m,s,c,cnt,head[35],fa[35];
bool vis[35],used[905],intree[905];
inline bool cmp(int x,int y); //对边进行排序
inline void add(int u,int v,int w); //加边
inline void init(); //多组数据初始化
inline int another(int x); //前向星中相反的边（从1开始）
// 并查集相关
inline void init2(); //初始化
int getfa(int x); //得到父亲
inline bool merge(int x,int y); //合并
void dfs1(int x); //求连通块
bool dfs2(int x,int f,int goal,int &now,int &e0); //求树上1->x
inline int kruskal(); //最小生成树
signed main()
{
cin>>t;
while (t--)
{
init();
mp["Park"]=1;
cin>>m;
for (int i=1;i<=m;i++)
{
cin>>a>>b>>c;
if (!mp.count(a)) mp[a]=++n;
if (!mp.count(b)) mp[b]=++n;
add(mp[a],mp[b],c);
add(mp[b],mp[a],c); //建边
}
cin>>s;
init2();
vis[1]=1;
int ans=0,tcnt=0;
for (int i=head[1];i;i=edge[i].next) //步骤1
{
int y=edge[i].to;
if (vis[y]) continue;
tcnt++; //连通块个数
v.clear();
dfs1(y);
ans+=kruskal(); //加上连通块内最小生成树的权值
}
v.clear();
for (int i=head[1];i;i=edge[i].next) v.emplace_back(i); //步骤2
ans+=kruskal();
int tot=s-tcnt;
while (tot--)
{
int mx=0,x0,e0; //e0=(u0,v0),x0=(1,x0)
for (int i=head[1];i;i=edge[i].next)
{
if (intree[i] || intree[another(i)]) continue;
int x=edge[i].to,z=edge[i].w,w=0,e;
dfs2(1,0,x,w,e); //得到最大权值w和那条边e
if (w-z>mx)
{
mx=w-z;
x0=i;
e0=e;
}
}
if (mx<=0) break;
intree[e0]=intree[another(e0)]=0;
intree[x0]=intree[another(x0)]=1; //换边
ans-=mx; //更新答案
}
cout<<"Total miles driven: "<<ans<<"\n";
if (t) puts(""); //注意最后一行不换行
}
return 0;
}
inline void add(int u,int v,int w)
{
edge[++cnt].to=v;
edge[cnt].from=u;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void init()
{
n=1;
cnt=0;
mp.clear();
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
memset(head,0,sizeof(head));
memset(intree,0,sizeof(intree));
}
inline int another(int x) { return ((x-1)^1)+1; }
inline bool cmp(int x,int y) { return edge[x].w<edge[y].w; }
inline void init2() { for (int i=1;i<=n;i++) fa[i]=i; }
int getfa(int x) { return x==fa[x] ? x : fa[x]=getfa(fa[x]); }
inline bool merge(int x,int y)
{
int gfx=getfa(x),gfy=getfa(y);
if (gfx==gfy) return 0;
fa[gfx]=gfy;
return 1;
}
void dfs1(int x)
{
vis[x]=1;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y!=1 && !used[i]) used[i]=used[another(i)]=1,v.emplace_back(i); //记录边
if (!vis[y]) dfs1(y);
}
}
inline int kruskal()
{
int ans=0;
sort(v.begin(),v.end(),cmp);
for (auto i:v)
{
int x=edge[i].from,y=edge[i].to,w=edge[i].w;
if (!merge(x,y)) continue;
ans+=w;
intree[i]=intree[another(i)]=1;
}
return ans;
}
bool dfs2(int x,int f,int goal,int &now,int &e0)
{
if (x==goal) return 1; //能到达终点
bool flag=0;
for (int i=head[x];i;i=edge[i].next)
{
if (!intree[i]) continue;
int y=edge[i].to,w=edge[i].w;
if (y==f) continue;
bool res=dfs2(y,x,goal,now,e0);
if (res && w>now) now=w,e0=i; //能到达终点才更新
flag|=res;
}
return flag;
}