题目链接：
POJ1639 Picnic Planning
洛谷 UVA1537 Picnic Planning
题目大意：
给出一个 (N) 个点的无向图，在满足树上节点1的度数 (leq k) 的条件下，求其最小生成树。
(1leq Nleq 20)
思路：
题目即求K度限制最小生成树，考虑这样一个算法：
- 首先划分删除节点1后产生的连通块，并在连通块中求各自的最小生成树。
- 找到块中距离节点1最近的点，并将其与节点1之间的边选上。
设连通块的个数为 (d) ，则我们还剩 (k-d) 的度数没有用，这时尝试将 (ans) 优化，将步骤3执行 (k-d) 次：
- 扫描节点1的剩下未加入出边，记边权为 (w) ，查找边所连接的点 (x) 在树上到节点1的路径中边权 (w') 最大的边 (e') ，找到使得 (w'-w) 最大的边 (e) ，若 (w'-wleq0) 则结束，否则 (ans-=w'-w) ，同时将 (e) 加入，并将 (e') 删除。
最后得到的就是所求答案，直接朴素维护的时间复杂度为 (O(n^3)) , (Link-Cut-Tree) 维护时间复杂度 (O(nlog^2n)) ，所以可以把数据加强到 (1leq Nleq 200000) （然后就变成了毒瘤题）。
细节：
细节就是有很多细节，但是比较好写。
Code:
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#define N 23
#define E 440
#define Inf 0x3f3f3f3f
using namespace std;
struct edge{
int u,v,len;
bool tf;
}e[E],maxx;
map<string,int> dict;
int cnt,n,fa[N];
int conn[N][N],ans;
bool tree[N][N];
int vis[N];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool cmp(edge a,edge b){
return a.len<b.len;
}
void dfs1(int x){
vis[x]=1;
for(int i=2;i<=n;i++)
if(conn[x][i]){
if(x<=i){
e[++cnt].u=x, e[cnt].v=i;
e[cnt].len=conn[x][i];
}
if(!vis[i])dfs1(i);
}
}
int dfs2(int x,int fa,int goal){
if(x==goal)return 0;
for(int i=1;i<=n;i++)
if(tree[x][i]&&i!=fa){
int temp=dfs2(i,x,goal);
if(~temp){
if(conn[x][i]>temp)maxx.u=x,maxx.v=i;
return max(conn[x][i],temp);
}
}
return -1;
}
bool Max(int &a,int b){
if(a>=b)return false;
a=b; return true;
}
bool Min(int & a,int b){
if(a<=b)return false;
a=b; return true;
}
int kruskal(){
int ret=0;
sort(e,e+cnt+1,cmp);
for(int i=0;i<=cnt;i++){
int x=find(e[i].u),y=find(e[i].v);
if(x==y)continue;
tree[e[i].u][e[i].v]=tree[e[i].v][e[i].u]=true;
ret+=e[i].len;
fa[x]=y;
}
return ret;
}
int main(){
int m,k;
int len,u,v;
string a,b;
cin>>m;
n=dict["Park"]=1;
for(int i=0;i<m;i++){
cin>>a>>b>>len;
if(!dict[a])dict[a]=++n;
if(!dict[b])dict[b]=++n;
u=dict[a],v=dict[b];
conn[u][v]=conn[v][u]=len;
}
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)fa[i]=i;
int deg=0;
vis[1]=2;
for(int i=1;i<=n;i++){
if(!conn[1][i]||vis[i])continue;
cnt=-1;
dfs1(i);
ans+=kruskal();
int minn=Inf,node;
for(int i=1;i<=n;i++)
if(vis[i]==1){
vis[i]=2;
if(conn[1][i]&&Min(minn,conn[1][i]))node=i;
}
tree[1][node]=tree[node][1]=true;
ans+=minn;
deg++;
}
cin>>k;
for(int i=0;i<k-deg;i++){
int delta=0,node;
edge del;
for(int i=1;i<=n;i++){
if(!conn[1][i])continue;
if(Max(delta,dfs2(1,-1,i)-conn[1][i])) node=i,del=maxx;
}
if(delta<=0)break;
ans-=delta;
tree[del.u][del.v]=tree[del.v][del.u]=false;
tree[1][node]=tree[node][1]=true;
}
cout<<"Total miles driven: "<<ans;
return 0;
}
洛谷上的AC代码在这（题目变成了多组数据）：https://www.luogu.com.cn/paste/wc62iorg