每个节点都限定度数的最大生成树怎么求？求代码和详解

/*************************************************

算法引入：

最小k度限制生成树,就是指有特殊的某一点的度不能超过k时的最小生成树

如果T是G的一个生成树且dT(v0)=k,则称T为G的k度限制生成树

G中权值和最小的k度限制生成树称为G的最小k度生成树

算法思想：

设特殊的那点为v0,先把v0删除,求出剩下连通图的所有最小生成树

假如有m棵最小生成树,那么这些生成树必定要跟v0点相连

也就是说这棵生成树的v0点至少是m度的

若m>k,条件不成立,无法找到最小k度限制生成树

若m<=k,则枚举m到k的所有最小生成树,即一步步将v0点的度加1,直到v0点的度为k为止

则v0点度从m到k的(k-m+1)棵最小生成树中最小的那棵即为答案

算法步骤：

(1)先求出最小m度限制生成树:

原图中去掉和V0相连的所有边(可以先存两个图,建议一个邻接矩阵,一个邻接表,用方便枚举边的邻接表来构造新图)

得到m个连通分量,则这m个连通分量必须通过v0来连接

则在图G的所有生成树中dT(v0)>=m

则当k<m时,问题无解

对每个连通分量求一次最小生成树

对于每个连通分量V’,用一条与V0直接连接的最小的边把它与V0点连接起来,使其整体成为一个生成树

就得到了一个m度限制生成树,即为最小m度限制生成树

(2)由最小m度限制生成树得到最小m+1度限制生成树

连接和V0相邻的点v,则可以知道一定会有一个环出现(因为原来是一个生成树)

只要找到这个环上的最大权边(不能与v0点直接相连)并删除,就可以得到一个m+1度限制生成树

枚举所有和V0相邻点v,找到替换后,增加权值最小的一次替换(如果找不到这样的边,就说明已经求出)

就可以求得m+1度限制生成树

如果每添加一条边,都需要对环上的边一一枚举,时间复杂度将比较高

用动态规划解决

设dp(v)为路径v0—v上与v0无关联且权值最大的边

定义father(v)为v的父结点,由此可以得到状态转移方程:

dp(v)=max(dp(father(v)),ω(father(v),v))

边界条件为dp[v0]=-∞(因为每次寻找的是最大边,所以-∞不会被考虑),dp[v’]=-∞|(v0,v’)∈E(T)

(3)当dT(v0)=k时停止(即当V0的度为k的时候停止),但不一定k的时候最优

算法实现：

并查集+kruskal

首先,每个连通分量的的最小生成树可以直接用一个循环,循环着Kruskal求出

这里利用了联通分量间的独立性,对每个连通分量分别求最小生成树,和放在一起求,毫不影响

而且kruskral算法保证了各连通分量边的有序性

找如厅销最小边的时候,可以用动态规划,也可以这么做：

先走一个循环,但我们需要逆过来加边,将与v0关联的所有边从小到达排序

然后将各连通分量连接起来,利用并查集可以保证每个连通分量只有一条边与v0相连

由于边已经从小到达排序,故与每个连通分量相连的边就是每个连通分量与v0相连中的最小边

然后求m+1度的最小生成树时,可以直接用DFS,最小生成树要一直求到k度,然后从伏冲中找出一个最优值

算法测试：

PKU1639(Picnic Planning)

题目大意:

给出m条边,每条边有两渣游个端点和一个权值

求这个图在满足以下条件的情况下的最小生成树

在所有点中,有一个特殊点Park,它在求得的最小生成树中的度必须小于等于某个值

**************************************************/

#include<iostream>

#include<string>

#include<cstdio>

#include<map>

#include<cstring>

#include<algorithm>

using namespace std

const int INF=99999999

const int N=100

int n,m//n为边的数量,m表示限度值

int cnt//计算出来的结点数

int set[N]

bool flag[N][N]

int G[N][N]

int ans

map<string,int>Map

struct node

{

  int x,y,v

} a[N*N]

struct edge

{

  int x,y,v

} dp[N]

int get_num(string s)//返回每个人对应结点

{

  if(Map.find(s)==Map.end())//没有搜索到该键值

  {

      Map[s]=++cnt//对应建图

  }

  // cout<<"  Map["<<s<<"]=="<<Map[s]<<endl

  return Map[s]

}

bool cmp(node a,node b)

{

  return a.v<b.v

}

int find_set(int x)

{

  if(x!=set[x])

      set[x]=find_set(set[x])

  return set[x]

}

inline void union_set(int x,int y)

{

  set[y]=x

}

void kruskal()//求m个连通分量的最小生成树

{

  for(int i=1i<=ni++)

  {

      if(a[i].x==1||a[i].y==1)

          continue

      int x=find_set(a[i].x)

      int y=find_set(a[i].y)

      if(x==y)

          continue

      flag[a[i].x][a[i].y]=flag[a[i].y][a[i].x]=true

      set[y]=x

      ans+=a[i].v

  }

}

void dfs(int x,int fa)

{

  for(int i=2i<=cnti++)

      if(i!=fa&&flag[x][i])

      {

          if(dp[i].v==-1)

          {

              if(dp[x].v>G[x][i])//dp(v)=max(dp(father(v)),ω(father(v),v))

              {

                  dp[i]=dp[x]

              }

              else

              {

                  dp[i].v=G[x][i]

                  dp[i].x=x

                  dp[i].y=i

              }

          }

          dfs(i,x)

      }

}

void init()

{

  ans=0

  cnt=1

  Map["Park"]=1

  memset(flag,0,sizeof(flag))

  memset(G,-1,sizeof(G))

  scanf("%d",&n)

  for(int i=1i<Ni++)//并查集初始化

      set[i]=i

  string s

  for(int i=1i<=ni++)

  {

      cin>>s

      a[i].x=get_num(s)

      cin>>s

      a[i].y=get_num(s)

      cin>>a[i].v

      if(G[a[i].x][a[i].y]==-1)

          G[a[i].x][a[i].y]=G[a[i].y][a[i].x]=a[i].v

      else//有重边

          G[a[i].x][a[i].y]=G[a[i].y][a[i].x]=min(G[a[i].y][a[i].x],a[i].v)

  }

  scanf("%d",&m)//m表示限度值

}

void solve()

{

  int tmp[N],Min[N]

  for(int i=1i<=cnti++)

      Min[i]=INF

  sort(a+1,a+1+n,cmp)

  kruskal()

  for(int i=2i<=cnti++)

  {

      if(G[1][i]!=-1)

      {

          int t=find_set(i)

          if(Min[t]>G[1][i])//求每个连通分量中和顶点1连接的最小权边

          {

              tmp[t]=i

              Min[t]=G[1][i]

          }

      }

  }

  int t=0//t表示最小限度

  for(int i=1i<=cnti++)

      if(Min[i]!=INF)

      {

          t++

          flag[1][tmp[i]]=flag[tmp[i]][1]=true

          ans+=G[1][tmp[i]]

      }

   

  for(int i=t+1i<=mi++)//枚举t到m的所有最小生成树,即一步步将v1点的度加1,直到v1点的度为m为止

  {

      memset(dp,-1,sizeof(dp))//dp[v]为路径v0—v上与v0无关联且权值最大的边

      dp[1].v=-INF

      for(int j=2j<=cntj++)

          if(flag[1][j])

              dp[j].v=-INF

      dfs(1,-1)

      int tmp,Min=INF

      for(int j=2j<=cntj++)

          if(G[1][j]!=-1)

          {

              if(Min>G[1][j]-dp[j].v)

              {

                  Min=G[1][j]-dp[j].v

                  tmp=j

              }

          }

      if(Min>=0)//找不到这样的边,就说明已经求出

          break

      flag[1][tmp]=flag[tmp][1]=true

      int x=dp[tmp].x

      int y=dp[tmp].y

      flag[x][y]=false

      flag[y][x]=false

      ans+=Min

  }

  printf("Total miles driven: %d\n",ans)

}

int main()

{

  freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin)

  init()

  solve()

  return 0

}

1、将图中所有边的边权变为相反数，再跑一遍最小生成树算法，相反数最小，原数就最大。

2、修改一下最小生成树算法：对于kruskal，将从小到大排序改为从大到小排序，对于prim，将每次选到所有培高蓝点代价最小的白点改为每次选到所有蓝点代价最大的点。

3、粗段邻接矩阵有对称性，且主对角元素不存在，遍历赋值的时候要注意。在一个图的所有生岩中誉成树中边权值和最大的生成树即为最大生成树。

---