• 牛客刷题之图论-最小生成树

    题目集链接

    目录

    1.黑暗城堡

    2.北极通讯网络

    3.新的开始

    4.构造完全图

    5.秘密的牛奶运输

    6.Tree

    7.最小生成树计数

    8.次小生成树

    1.黑暗城堡

    先求出最小生成树的每个边权，然后枚举每个点在不改变最小权值的情况下，能由多少个点转移过来，然后答案就是这些点个数的乘积

    1. #include
    2. using namespace std;
    3. const int N=1e3+10,mod=2147483647;
    4. int w[N][N],dist[N];
    5. bool st[N];
    6. int n,m;
    7. int prim()//先prim算法预处理处理最小生成树
    8. {
    9.     memset(dist,0x3f,sizeof dist);
    10.     dist[1]=0;
    11.     for(int i=0;i
    12.     {
    13.         int t=-1;
    14.         for(int j=1;j<=n;j++)
    15.             if(!st[j]&&(t==-1||dist[j]
    16.                  t=j;
    17.        st[t]=true;
    18.        for(int j=1;j<=n;j++)  dist[j]=min(dist[j],dist[t]+w[t][j]);
    19.     }
    20.     int res=1;
    21.     for(int i=2;i<=n;i++)//枚举每个点在不改变最小权值的情况下，能由多少个点转移过来
    22.     {
    23.         int sum=0;
    24.         for(int j=1;j<=n;j++)
    25.              if(w[i][j]!=0x3f3f3f3f&&dist[i]==dist[j]+w[i][j]) sum++;
    26.         res=(long long)res*sum%mod;//答案就是他们的乘积
    27.     }
    28.     return res;
    29. }
    30. int main()
    31. {
    32.     memset(w,0x3f,sizeof w);
    33.     scanf("%d%d",&n,&m);
    34.     int a,b,c;
    35.     while(m--)
    36.     {
    37.         scanf("%d%d%d",&a,&b,&c);
    38.         w[a][b]=w[b][a]=c;
    39.     }
    40.     cout<<prim()<
    41.     return 0;
    42. }

    2.北极通讯网络

    先把小的先贪了，假如剩下连通块小于等于k个了，说明后面k个直接给他们装卫星了，不用在接无线发电机了，所以最小的d就是枚举到的w

    1. #include
    2. using namespace std;
    3. const int N=510,M=N*N;
    4. bool st[N];
    5. int n,m,k;
    6. struct
    7. {
    8.     int x,y;
    9. }q[N];
    10. struct Edge
    11. {
    12.     int a,b;
    13.     double w;
    14.     bool operator <(const Edge &W)const
    15.     {
    16.         return w
    17.     }
    18. }e[M];
    19. int p[N];
    20. int find(int x)//并查集
    21. {
    22.     if(p[x]!=x) p[x]=find(p[x]);
    23.     return p[x];
    24. }
    25. double get(int i,int j)//两点间距离
    26. {
    27.     return sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
    28. }
    29. int main()
    30. {
    31.     int cnt=0;
    32.     cin>>n>>k;
    33.     for(int i=0;i>q[i].x>>q[i].y,p[i]=i;
    34.     for(int i=0;i
    35.         for(int j=i;j
    36.             e[cnt++]={i,j,get(i,j)};
    37.     //Kruskal算法求最小生成树
    38.     sort(e,e+cnt);//将边从小到大排序
    39.     int ans=n;
    40.     double res=0;
    41.     for(int i=0;i//枚举边
    42.     {
    43.         if(ans<=k) break;//假如后面可以直接装卫星了，则直接跳出
    44.         int a=e[i].a,b=e[i].b;
    45.         double w=e[i].w;
    46.         int pa=find(a),pb=find(b);
    47.         if(pa!=pb)
    48.         {
    49.             ans--;
    50.             p[pa]=pb;
    51.         }
    52.         res=w;//更新d
    53.     }
    54.     printf("%.2lf\n",res);
    55.     return 0;
    56. }

    3.新的开始

    建立一个虚拟原点0，从0到i加条v的边，表示要在i这个位置修建发电站得花费v的费用，然后跑一遍最小生成树即可

    1. #include
    2. using namespace std;
    3. const int N=310;
    4. int w[N][N],dist[N];
    5. bool st[N];
    6. int n,m;
    7. int prim()//prim算法求最小生成树
    8. {
    9.     memset(dist,0x3f,sizeof dist);
    10.     dist[0]=0;
    11.     int res=0;
    12.     for(int i=0;i<=n;i++)
    13.     {
    14.         int t=-1;
    15.         for(int j=0;j<=n;j++)
    16.             if(!st[j]&&(t==-1||dist[j]
    17.               t=j;
    18.         res+=dist[t];
    19.         st[t]=true;
    20.         for(int j=0;j<=n;j++) dist[j]=min(dist[j],w[t][j]);
    21.     }
    22.     return res;
    23. }
    24. int main()
    25. {
    26.  
    27.     scanf("%d",&n);
    28.     int c;
    29.     for(int i=1;i<=n;i++) scanf("%d",&c),w[0][i]=c;
    30.     for(int i=1;i<=n;i++)
    31.         for(int j=1;j<=n;j++)
    32.         {
    33.             scanf("%d",&c);
    34.             w[i][j]=c;
    35.         }
    36.     printf("%d\n",prim());
    37.     return 0;
    38. }

    4.构造完全图

    讲解的清楚 ：传送门

    分析
    假设有如下图两个集合 x xx & y yy。因为要构造一个完全图，所以应该将x xx中的s [ x ] s[x]s[x]个节点与y yy中的s [ y ] s[y]s[y]个节点一一连接即连接s [ x ] ∗ s [ y ] − 1 s[x] * s[y] - 1s[x]∗s[y]−1（此处减一是为了在后面单独处理原图中的d i s [ i ] . w dis[i].wdis[i].w）个节点，为了保证此完全图的最小生成树所以要用( s [ x ] ∗ s [ y ] − 1 ) ∗ ( d i s [ i ] . w + 1 ) (s[x] * s[y] - 1) * (dis[i].w + 1)(s[x]∗s[y]−1)∗(dis[i].w+1)，最后加上原图中的d i s [ i ] . w dis[i].wdis[i].w。

     解题思路：
    1、用Kruskal模拟生成树
    2、两个集合合成时，构建局部完全图，即假如一个集合的成员点数为n1，另一个为n2,则需要构建n1*n2条边，由贪心思想可以构建一条最小长度d，其余构建长度都为d+1，所以有sum+=d(n1*n2)-1;

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10;
    5. ll res;
    6. int n;
    7. struct Edge
    8. {
    9.     int a,b,w;
    10.     bool operator <(const Edge&W)const
    11.     {
    12.         return w
    13.     }
    14. }e[N];
    15. int p[N],s[N];
    16. int find(int x)
    17. {
    18.     if(p[x]!=x) p[x]=find(p[x]);
    19.     return p[x];
    20. }
    21. int main()
    22. {
    23.     scanf("%d",&n);
    24.     for(int i=0;i-1;i++)
    25.     {
    26.         int a,b,c;
    27.         scanf("%d%d%d",&a,&b,&c);
    28.         e[i]={a,b,c};
    29.     }
    30.     for(int i=1;i<=n;i++) p[i]=i,s[i]=1;
    31.     sort(e,e+n-1);
    32.     for(int i=0;i-1;i++)
    33.     {
    34.         int a=find(e[i].a),b=find(e[i].b),w=e[i].w;
    35.         if(a!=b)
    36.         {
    37.             p[a]=b;//把集合a合并到b中
    38.             res+=(ll)(s[a]*s[b]-1)*(w+1)+w;//答案加上需要添加的边和已经有了的的边
    39.             s[b]+=s[a];//把a集合的个数+到b中
    40.         }
    41.     }
    42.     printf("%lld\n",res);
    43.     return 0;
    44. }

    5.秘密的牛奶运输

    这题就是问次小生成树，我们可以先求好最小生成树，然后标记树边与非树边，在求一遍最小生成树中，两两路径的最大值，也即一个点到另一个点中的路径的最大值，然后枚举非树边，看看能不能把这条边加进来，使得树边权值变大，然后求一遍所有的生成树的最小值

    这题因为不会存在环，所以可以这样做，假如有环就不行了

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=5e2+10,M=1e4+10;
    5. int h[N],e[M],ne[M],w[M],idx;
    6. int n,m;
    7. int dist[N][N];
    8. ll sum=0,res=1e18;
    9. struct Edge
    10. {
    11.     int a,b,w;
    12.     bool f;
    13.     bool operator <(const Edge&W)const
    14.     {
    15.         return w
    16.     }
    17. }edge[M];
    18. void add(int a,int b,int c)
    19. {
    20.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    21. }
    22. int p[N];
    23. int find(int x)
    24. {
    25.     if(p[x]!=x) p[x]=find(p[x]);
    26.     return p[x];
    27. }
    28. void kruskal()
    29. {
    30.     for(int i=1;i<=n;i++) p[i]=i;
    31.     for(int i=1;i<=m;i++)
    32.     {
    33.         int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
    34.         if(a!=b)
    35.         {
    36.             p[a]=b;
    37.             sum+=w;
    38.             add(a,b,w),add(b,a,w);//建立树边
    39.             edge[i].f=true;
    40.         }
    41.     }
    42. }
    43. void dfs(int u,int f,int maxd,int d[])//当前第u位，父节点是f，路径最大值是maxd,d是当前是距离数组
    44. {
    45.     d[u]=maxd;
    46.     for(int i=h[u];~i;i=ne[i])
    47.     {
    48.         int j=e[i];
    49.         if(j==f) continue;
    50.         dfs(j,u,max(maxd,w[i]),d);//枚举下一个点
    51.     }
    52. }
    53. int main()
    54. {
    55.     memset(h,-1,sizeof h);
    56.     scanf("%d%d",&n,&m);
    57.     for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w);
    58.     sort(edge+1,edge+m+1);
    59.     kruskal();//求一遍最小生成树，并建立好最小生成树
    60.     for(int i=1;i<=n;i++) dfs(i,-1,0,dist[i]);//求一下树中两两路径的最大值
    61.     for(int i=1;i<=m;i++)//枚举非树边进行替换
    62.         if(!edge[i].f)
    63.         {
    64.             int a=edge[i].a,b=edge[i].b,w=edge[i].w;
    65.             if(dist[a][b]//假如可以替换
    66.             {
    67.                 res=min(res,sum+w-dist[a][b]);
    68.             }
    69.         }
    70.     printf("%lld\n",res);
    71.     return 0;
    72. }

    6.Tree

    传送门

    最小生成树无法控制白边的选取数量
    于是我们就对白边增加/减少一定的值x
    然后做Kruskal，记录白边的值
    如果选取的数量大于need说明白边多了，则增加x（少选白边）
    小于need说明白边少了，则减少x（多选白边）
    如果刚好等于need，我们选择增加x
    因为在能保证白边选取数量为need的时候，我们所选择的白边实际上已经固定
    当x增加，白边相当于整体向后挪动，这样就可以使选择的黑边尽可能小
    这样一来，我们选择的黑边是最小的，白边也是最小的，结果自然最优

    ps在排序的时候边权相同时优先选择白边（和上述理解类似，请读者自行解决）

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10;
    5. int n,m,k,sum;
    6. struct Edge
    7. {
    8.     int a,b,w,type;
    9.     bool operator <(const Edge&W)const
    10.     {
    11.         if(w==W.w) return type
    12.         return w
    13.     }
    14. }e[N];
    15. int a[N],b[N],w[N],type[N];
    16. int p[N];
    17. int find(int x)
    18. {
    19.     if(p[x]!=x) p[x]=find(p[x]);
    20.     return p[x];
    21. }
    22. bool judge(int x)
    23. {
    24.     int cnt=0;
    25.     sum=0;
    26.     for(int i=0;i<=n;i++) p[i]=i;
    27.     for(int i=1;i<=m;i++)//先把数全部copy过来
    28.     {
    29.         e[i]={a[i],b[i],w[i],type[i]};
    30.         if(!e[i].type) e[i].w+=x;//假如是白色，则减去
    31.     }
    32.     sort(e+1,e+m+1);
    33.     for(int i=1;i<=m;i++)
    34.     {
    35.         int pa=find(e[i].a),pb=find(e[i].b);
    36.         if(pa!=pb)
    37.         {
    38.             if(!e[i].type) cnt++;//记录白色的边有多少条
    39.             p[pa]=pb;
    40.             sum+=e[i].w;//数的总权值
    41.         }
    42.     }
    43.     return cnt>=k;
    44. }
    45. int main()
    46. {
    47.     scanf("%d%d%d",&n,&m,&k);
    48.     for(int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i],&b[i],&w[i],&type[i]);//先存下来数据
    49.     int l=-100,r=100,res;
    50.     while(l<=r)//二分
    51.     {
    52.         int mid=l+r>>1;
    53.         if(judge(mid)) l=mid+1,res=sum-k*mid;//假如白色的数多了，则变大点，答案就是总得出来的树总权值减去加上的k条白色权值
    54.         else r=mid-1;
    55.     }
    56.     printf("%d\n",res);
    57.     return 0;
    58. }

    7.最小生成树计数

    衍生至生成树计数，这题就问最小生成树的个数有多少个，有两种做法 

    借鉴于图论 —— 生成树 —— 生成树计数_Alex_McAvoy的博客-CSDN博客_生成树计数

    1. #include
    2. using namespace std;
    3. const int N=1e2+10,M=1e3+10,mod=31011;
    4. int n,m;
    5. int sum;
    6. struct Edge
    7. {
    8.     int a,b,w;
    9.     bool operator <(const Edge&W)const
    10.     {
    11.         return w
    12.     }
    13. }e[M];
    14. struct
    15. {
    16.     int l,r,cnt;
    17. }a[M];//记录不同的边在最小生成树中需要的条数
    18. int cnta;
    19. int p[N];
    20. int find(int x)//没有路径压缩的并查集
    21. {
    22.     if(p[x]!=x) return find(p[x]);
    23.     return p[x];
    24. }
    25. int kruskal()//求最小生成树
    26. {
    27.     int cnt=0;
    28.     sort(e+1,e+1+m);
    29.     for(int i=1;i<=n;i++) p[i]=i;
    30.     for(int i=1;i<=m;i++)
    31.     {
    32.         int fa=find(e[i].a),fb=find(e[i].b),w=e[i].w;
    33.         if(e[i-1].w!=w) a[cnta].r=i-1,a[++cnta].l=i;//假如不同边则加进来
    34.         if(fa!=fb)
    35.         {
    36.             p[fa]=fb;
    37.             a[cnta].cnt++;
    38.             cnt++;
    39.         }
    40.     }
    41.     a[cnta].r=m;
    42.     return cnt;
    43. }
    44. void dfs(int x,int now,int num)//处理到第x条边，现在的点是now，现在已经用了的边是num
    45. {
    46.     if(now==a[x].r+1)
    47.     {
    48.         if(num==a[x].cnt) sum++;//假如这num条也能构成新的最小生成树，则sum++
    49.         return;
    50.     }
    51.     int fa=find(e[now].a),fb=find(e[now].b);
    52.     if(fa!=fb)//假如不在一个集合才能选这条边
    53.     {
    54.         p[fa]=fb;//把这个集合合并在一起
    55.         dfs(x,now+1,num+1);//选这条边
    56.         p[fa]=fa;//回溯，把变了的改回来
    57.     }
    58.     dfs(x,now+1,num);//不选择这条边
    59. }
    60. int main()
    61. {
    62.     scanf("%d%d",&n,&m);
    63.     for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
    64.     int t=kruskal();
    65.     if(t!=n-1)//假如不能构成一棵树
    66.     {
    67.         puts("0");
    68.         return 0;
    69.     }
    70.     int res=1;
    71.     for(int i=1;i<=n;i++) p[i]=i;//初始化集合，也即并查集
    72.     for(int i=1;i<=cnta;i++)//枚举所有不同的边
    73.     {
    74.         sum=0;
    75.         dfs(i,a[i].l,0);//求一下这个边能有多少中方案
    76.         res=res*sum%mod;//答案就是每种边之积
    77.         for(int j=a[i].l;j<=a[i].r;j++)//把边重新加入到最小生成树中
    78.         {
    79.             int fa=find(e[j].a),fb=find(e[j].b);
    80.             if(fa!=fb) p[fa]=fb;
    81.         }
    82.     }
    83.     printf("%d\n",res);
    84.     return 0;
    85. }

    8.次小生成树

    借鉴大佬：传送门

    lca倍增O(logn)求新加入非树边边的两点a,b间的最大边和最小边

      定理:对于一张无向图,如果存在最小生成树和次小生成树,那么对于任何一颗最小生成树都存在一颗次小生成树
           使得这两棵树只有一条边不同 

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f;
    5. int p[N];//并查集
    6. int h[N],e[M],ne[M],w[M],idx;
    7. int depth[N],d1[N][17],d2[N][17],f[N][17];//depth是深度，d1是某个点走2^j次方步的最大值，d2是次大值，f是某个点走2^k次方步所到达的点
    8. int q[N];
    9. int n,m;
    10. struct Edge
    11. {
    12.     int a,b,w;
    13.     bool used;//用来标记是否是树边
    14.     bool operator <(const Edge &t) const
    15.     {
    16.         return w
    17.     }
    18. }edge[M];
    19. void add(int a,int b,int c)
    20. {
    21.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    22. }
    23. int find(int x)
    24. {
    25.     if(p[x]!=x) p[x]=find(p[x]);
    26.     return p[x];
    27. }
    28. ll kruskal()//求最小生成树
    29. {
    30.     memset(h,-1,sizeof h);//初始化
    31.     for(int i=1;i<=n;i++) p[i]=i;//初始化
    32.     sort(edge,edge+m);//排序
    33.     ll res=0;
    34.     for(int i=0;i
    35.     {
    36.         int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
    37.         if(a!=b)//假如不在一个集合
    38.         {
    39.             p[a]=b;//合并成一个集合
    40.             res+=w;//加上这条最小生成树的边
    41.             edge[i].used=true;//标记一下是树边
    42.             add(edge[i].a,edge[i].b,w),add(edge[i].b,edge[i].a,w);//建树图
    43.         }
    44.     }
    45.     return res;//返回最小生成树的权值和
    46. }
    47. void bfs()//求 深度 最大值 次大值  每个点走几步由那个点更新过来
    48. {
    49.      memset(depth,0x3f,sizeof depth);
    50.      depth[0]=0,depth[1]=1;//0号点是避免跳出去，1号点初始化深度为1
    51.      int hh=0,tt=0;
    52.      q[0]=1;//1号点入队
    53.      while(hh<=tt)
    54.      {
    55.          int t=q[hh++];
    56.          for(int i=h[t];~i;i=ne[i])
    57.          {
    58.              int j=e[i];
    59.              if(depth[j]>depth[t]+1)//假如没有更新过
    60.              {
    61.                  depth[j]=depth[t]+1;//则更新深度
    62.                  q[++tt]=j;//把这个点入队
    63.                  f[j][0]=t;//j这个点走2^0=1步是t
    64.                  d1[j][0]=w[i],d2[j][0]=-INF;//j这个点向上走2^0=1步的最大值是w[i],次大没有标记为负无穷
    65.                  for(int k=1;k<=16;k++)//更新跳到的点
    66.                  {
    67.                      int anc=f[j][k-1];//表示由那个点跳过来的
    68.                      int d[4]={d1[anc][k-1],d2[anc][k-1],d1[j][k-1],d2[j][k-1]};//把j~anc~k的最大次大加到d中
    69.                      f[j][k]=f[anc][k-1];//更新跳的点
    70.                      d1[j][k]=d2[j][k]=-INF;//先初始化为负无穷
    71.                      for(int u=0;u<4;u++)//求一遍最大和次大
    72.                      {
    73.                          int dist=d[u];
    74.                          if(dist>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=dist;
    75.                          else if(dist!=d1[j][k]&&dist>d2[j][k]) d2[j][k]=dist;
    76.                      }
    77.                  }
    78.              }
    79.          }
    80.      }
    81. }
    82. int lca(int a,int b,int w)//用来求最大值与次大值能否更新
    83. {
    84.     static int d[2*N];
    85.     int cnt=0;
    86.     if(depth[a]swap(a,b);//假如a深度低，则交换
    87.     for(int k=16;k>=0;k--)//让a与b同个深度
    88.       if(depth[f[a][k]]>=depth[b])//假如还是大，则继续跳
    89.       {
    90.           //把他们跳过的位置的最大值与次大值都记录下来
    91.           d[cnt++]=d1[a][k];
    92.           d[cnt++]=d2[a][k];
    93.           a=f[a][k];//更新跳的点
    94.       }
    95.     if(a!=b)//假如还没跳到一起，也就是没找到最近公共祖宗
    96.     {
    97.        for(int k=16;k>=0;k--)//让a和b一起跳
    98.           if(f[a][k]!=f[b][k])
    99.           {
    100.               //把他们跳过的位置的最大值与次大值都记录下来
    101.               d[cnt++]=d1[a][k];
    102.               d[cnt++]=d2[a][k];
    103.               d[cnt++]=d1[b][k];
    104.               d[cnt++]=d2[b][k];
    105.              a=f[a][k],b=f[b][k];//更新跳过的位置
    106.           }
    107.           //最后也要把跳到最近公共祖先的位置也记录下来
    108.           d[cnt++]=d1[a][0];
    109.           d[cnt++]=d2[a][0];
    110.           d[cnt++]=d1[b][0];
    111.           d[cnt++]=d2[b][0];
    112.     }
    113.     int dist1=-INF,dist2=-INF;
    114.     for(int i=0;i//求一遍最大值和次大值
    115.     {
    116.         int dist=d[i];
    117.         if(dist>dist1) dist2=dist1,dist1=dist;
    118.         else if(dist!=dist1&&dist>dist2) dist2=dist;
    119.     }
    120.     if(w>dist1) return w-dist1;//假如最大值可以用来更新
    121.     if(w>dist2) return w-dist2;//反之次大值可以用来更新
    122.     return INF;//反之为正无穷
    123. }
    124. int main()
    125. {
    126.    scanf("%d%d",&n,&m);
    127.    for(int i=0;i
    128.    {
    129.       int a,b,w;
    130.       scanf("%d%d%d",&a,&b,&w);
    131.       edge[i]={a,b,w};
    132.    }
    133.    ll sum=kruskal();//求一下最小生成树的权值和
    134.    bfs();//求深度 最大值 次大值 更新的点
    135.    ll res=1e18;
    136.    for(int i=0;i
    137.       if(!edge[i].used)//假如是非树边
    138.       {
    139.           int a=edge[i].a,b=edge[i].b,w=edge[i].w;
    140.           res=min(res,sum+lca(a,b,w));//求一遍最大值与次大值能否用来更新
    141.       }
    142.     printf("%lld\n",res);
    143.     return 0;
    144. }

  • 相关阅读:
    【Flink实战】Flink对接Kafka Connetor使用docker部署kafka
    ElasticSearch集群搭建及启动异常的问题
    LVDS 转 MIPI 主桥芯片1 概述 GM8829C
    长方柱类（类和对象）Java
    关于python的odl库的相关问题解决
    Iterable、Collection、List等接口
    Springboot泊车收费管理系统97439计算机毕业设计-课程设计-期末作业-毕设程序代做
    前端Vue2项目搭建过程
    【c++】cpp类和对象
    Java NIO 学习
  • 原文地址：https://blog.csdn.net/m0_63729880/article/details/127793937