先决条件 : 掌握 最小生成树 Kruskal 算法 , 基础的 dp 能力

最小 K 度生成树

定义 :

给定一张图，n 个点，m 条边，求一棵满足如下条件的生成树：

1) 节点 x 的度不超过 k
2) 在 1) 的条件下所求生成树最小

求最小 k 度生成树的思想：

将 x 删除，原图成为几个连通块，对每个连通块求最小生成树
假设有 m 个连通块，即有 m 棵最小生成树，且这些生成树必定与节点 x 相连

所以，所求的生成树至少是 m 度的
回到原问题，求最小 k 度生成树，分类讨论：

m > k ，无法满足条件，不存在最小 k 度生成树

m <= k ，最小 k 度生成树即为 节点 x 的度在 m ~ k 间的所有生成树最小的哪个

解法步骤：

1) 对去掉 x 及 x 相连的边后的各个连通块求最小生成树
该操作等价于直接对整个图用 Kruskal 算法求最小生成树

为什么？原因如下 :

Kruskal 算法是通过从小到大枚举边，并判断边连接的两点是否在同一集合，来决定是否加边的
所以尽管 Kruskal 保证了最先加入的边所构成的答案最优，但不能判断原图是否只构成一棵树
因为各个点集相互独立，而我们只是将可加入的边加入集合而已

但这个性质可以被我们利用
我们对于每个连通块都要求最小生成树，且每个连通块互不影响
那么我们可以直接对整个图用 Kruskal 算法，就求出了每个连通块的最小生成树

代码实现 :

//关于初始数组含义：

struct EDGE {int x,y,z;} e[N*N],maxn[N];
//e[] : 边表    maxn[i] : dp 中 i 到 X 路径中权值最大的边
int n,k,X,m=0,tot=1,ans=0;
//n : 边数       k : X 的度限制       X : 限制点  
//m : 去掉 X 及 X 的连边后连通块的个数       tot : 节点数     ans : 最小 k 度生成树的值 
int fa[N],minn[N],po[N];
//fa[] : 并查集保存的父节点       minn[] : 每棵最小生成树到 x 的最短距离        po :  在每棵最小生成树中，到 X 距离最短的点的位置 
int mp1[N][N],mp2[N][N];
//mp1 : 邻接矩阵存图       mp2 : 新的邻接矩阵模拟过程 

// 步骤 1) 的实现 : 

bool cmp(EDGE a,EDGE b) {return a.z<b.z;}
int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);}

inline void solve1()
//Kruskal
{
    for(int i=1;i<=tot;i++) fa[i]=i;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(e[i].x==X||e[i].y==X) continue;
        //去掉 X 及 X 相连的边 
        int x=get(e[i].x),y=get(e[i].y);
        if(x!=y)
        {
            mp2[e[i].x][e[i].y]=mp2[e[i].y][e[i].x]=1;
            //建边
            fa[y]=x;ans+=e[i].z; 
        }
    }
}

2) 求最小 m 度生成树，m为连通块个数

1) 步骤之后，我们其实并不知道生成了多少个最小生成树 (假设为 m 个)

我们直接枚举除 x 外的点，在 1) 中我们通过并查集求得每个连通块的根节点
我们以根节点作为一个最小生成树的特征，来保存每个最小生成树到 x 的最短距离

我们再次枚举除 x 外的点，就能求得 m 的数目及最小 m 度生成树的大小 (假设存在)

代码实现 :

// 步骤 2) 的实现 : 

inline void solve2()
{
    memset(minn,63,sizeof(minn));
    for(int i=1;i<=tot;i++)
    {
        if(i==X) continue;
        if(mp1[i][X]!=-1)
        {
            int rt=get(i);
            //根节点为标志,代表整棵最小生成树 
            if(mp1[i][X]<minn[rt])
            {
                po[rt]=i;
                minn[rt]=mp1[i][X];
            }
        }
    }

    for(int i=1;i<=tot;i++)
        if(minn[i]!=minn[0])
        {
            ++m;
            //最小生成树 (连通块) 个数
            mp2[X][po[i]]=mp2[po[i]][X]=1;
            ans+=mp1[X][po[i]];
        }
}

3) 试着将 m 度扩展到 k 度，最小 k 度生成树就在 m ~ k 之中

如果每次都重新求最小生成树，时间复杂度太高，不能接受

我们考虑到每次只增加一条边，也就是多出了一个环，更新答案只需在环上找到权值最大的边并除去

对于增加的边，我们进行分析：
·这条边连接 x 与另一点 y
·y 所在的点集先前已经与 x 连通 (在求解最小 m 度生成树时)
·生成环上的最大边一定在 y 到 x 的路径中

所以问题的关键在于 y 的处理。我们需要得到的信息是 ：y 到 x 的路径中权值最大的边
该问题可以用 dp 处理，显然可以得到 maxn(y)=max(e(y<–>fa[y]),maxn(fa[y]));

至此，问题得以解决

代码实现 :

// 步骤 3) 的实现 :

void dfs(int x,int fro)
//处理出每个点到 X 路径中权值最大的边 
{
    for(int i=1;i<=tot;i++)
    {
        if(i==X) continue;
        if(mp2[x][i]&&i!=fro)
        {
            if(maxn[i].z==-1)
            {
                if(mp1[x][i]<maxn[x].z) maxn[i]=maxn[x];
                else maxn[i].x=x,maxn[i].y=i,maxn[i].z=mp1[x][i];
            }
            dfs(i,x);
        }
    }

}

inline void solve3()
{
    for(int i=m+1;i<=k;i++)
    {
        memset(maxn,-1,sizeof(maxn)); maxn[X].z=-inf;
        for(int j=1;j<=tot;j++)
            if(j!=X&&mp2[X][j]) maxn[j].z=-inf;
        //与 X 相连的边为 dfs 边界，赋值为 -OO 
        dfs(1,0);
        int num=0,res=inf;
        for(int j=1;j<=n;j++)
        {
            if(j==X) continue;
            if(mp1[X][j]!=-1&&mp1[X][j]-maxn[j].z<res) {res=mp1[X][j]-maxn[j].z;num=j;}
        }

        if(res>=0) break;
        //答案已最优 
        mp2[X][num]=mp2[num][X]=1;
        mp2[maxn[num].x][maxn[num].y]=mp2[maxn[num].y][maxn[num].x]=0;
        //加边 & 清边
        ans+=res; 
    }
}

例题 AcWing 347 野餐规划

https://www.acwing.com/problem/content/349/

题目大意 :

求以 Park 为 X 节点的最小 K 度生成树

分析 :

虽然在定义中 X 为任意节点，但在实际操作中，我们常常把 X 设为 1 (方便)

这题就是一道模板题

读入为字符串，用 map 标记一下，处理出节点，然后套模板

代码 :

#include<bits/stdc++.h>
using namespace std;

const int N=210,inf=1e9;

struct EDGE {int x,y,z;}e[N*N],maxn[N];

int n,k,m=0,tot=1,ans=0;
int fa[N],minn[N],po[N];
int mp1[N][N],mp2[N][N];

char name[N];

map<string,int> H;

inline void init()
{
    scanf("%d",&n);getchar();H["Park"]=1;
    memset(mp1,-1,sizeof(mp1));

    for(int i=1,z;i<=n;i++)
    {
        scanf("%s",name);
        if(H.find(name)==H.end()) H[name]=++tot; e[i].x=H[name];
        scanf("%s",name);
        if(H.find(name)==H.end()) H[name]=++tot; e[i].y=H[name];
        scanf("%d",&z);e[i].z=z; getchar();
        if(mp1[e[i].x][e[i].y]==-1) mp1[e[i].x][e[i].y]=mp1[e[i].y][e[i].x]=z;
        else mp1[e[i].x][e[i].y]=mp1[e[i].y][e[i].x]=min(mp1[e[i].x][e[i].y],z);
    }
    scanf("%d",&k);
}

bool cmp(EDGE a,EDGE b) {return a.z<b.z;}
int get(int x) {return fa[x]==x?x:fa[x]=get(fa[x]);}

inline void solve1()
{
    for(int i=1;i<=tot;i++) fa[i]=i;
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(e[i].x==1||e[i].y==1) continue;
        int x=get(e[i].x),y=get(e[i].y);
        if(x!=y)
        {
            mp2[e[i].x][e[i].y]=mp2[e[i].y][e[i].x]=1;
            fa[y]=x;ans+=e[i].z; 
        }
    }
}

inline void solve2()
{
    memset(minn,63,sizeof(minn));
    for(int i=2;i<=tot;i++)
        if(mp1[i][1]!=-1)
        {
            int rt=get(i);
            if(mp1[i][1]<minn[rt])
            {
                po[rt]=i;
                minn[rt]=mp1[i][1];
            }
        }
    for(int i=1;i<=tot;i++)
        if(minn[i]!=minn[0])
        {
            ++m;
            mp2[1][po[i]]=mp2[po[i]][1]=1;
            ans+=mp1[1][po[i]];
        }
}

void dfs(int x,int fro)
{
    for(int i=2;i<=tot;i++)
        if(mp2[x][i]&&i!=fro)
        {
            if(maxn[i].z==-1)
            {
                if(mp1[x][i]<maxn[x].z) maxn[i]=maxn[x];
                else maxn[i].x=x,maxn[i].y=i,maxn[i].z=mp1[x][i];
            }
            dfs(i,x);
        }
}

inline void solve3()
{
    for(int i=m+1;i<=k;i++)
    {
        memset(maxn,-1,sizeof(maxn)); maxn[1].z=-inf;
        for(int j=2;j<=tot;j++)
            if(mp2[1][j]) maxn[j].z=-inf;
        dfs(1,0);
        int num=0,res=inf;
        for(int j=2;j<=n;j++)
            if(mp1[1][j]!=-1&&mp1[1][j]-maxn[j].z<res)
            {
                res=mp1[1][j]-maxn[j].z;
                num=j;
            }
        if(res>=0) break;
        mp2[1][num]=mp2[num][1]=1;
        mp2[maxn[num].x][maxn[num].y]=mp2[maxn[num].y][maxn[num].x]=0;
        ans+=res; 
    }
}

int main()
{
    init();
    solve1();
    solve2();
    solve3();
    printf("Total miles driven: %d\n",ans);
    return 0;
}