Slim Span POJ 3522 （最小差值生成树）

客官°小女子只卖身不卖艺 2023-10-11 09:36 23阅读 0赞

题意：

最小生成树找出来最小的边权值总和使得n个顶点都连在一起。那么这找出来的边权值中的最大权值和最小权值之差就是本题的结果

但是题目要求让这个输出的结果最小，也就是差值最小。那么这就不是最小生成树了

题解：

思路1、

让所有边这个权值从小到大排序，之后一个权值一个权值的枚举，枚举那个权值就证明我们肯定会用到这个权值，然后让这个权值和其他边的权值做差

用这个差来代替原来的权值，再去进行最小生成树

思路2、

让所有边这个权值从小到大排序，之后一个权值一个权值的枚举，枚举到的这个权值代表我们用来连接的n个点的所有边中权值最小值就是它

然后再进行最小生成树，只要边的权值小于它的都不用这条边

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 #include<vector>
     6 #include<queue>
     7 using namespace std;
     8 const int maxn=105;
     9 const int INF=0x3f3f3f3f;
    10 int n,m,fa[maxn];
    11 struct shudui
    12 {
    13     int u,v,w;
    14 } e[maxn*maxn];
    15 bool mmp(shudui x,shudui y)
    16 {
    17     return x.w<y.w;
    18 }
    19 int finds(int x)
    20 {
    21     if(x!=fa[x])
    22     {
    23         int y=finds(fa[x]);
    24         fa[x]=y;
    25         return y;
    26     }
    27     return x;
    28 }
    29 void init()
    30 {
    31     for(int i=1; i<=n; ++i)
    32     {
    33         fa[i]=i;
    34     }
    35 }
    36 int main()
    37 {
    38     while(~scanf("%d%d",&n,&m))
    39     {
    40         if(!n && !m) break;
    41         //memset(mp,0,sizeof(mp));
    42         for(int i=1; i<=m; ++i)
    43         {
    44             int u,v,w;
    45             scanf("%d%d%d",&u,&v,&w);
    46             e[i].u=u;
    47             e[i].v=v;
    48             e[i].w=w;
    49         }
    50         e[0].w=-1;
    51         init();
    52         sort(e+1,e+1+m,mmp);
    53         int minn=INF,flag=0;
    54         if(m==0) flag=1;
    55         for(int i=1; i<=m; ++i)
    56         {
    57             if(e[i].w!=e[i-1].w)
    58             {
    59                 init();
    60                 int ans=0;
    61                 for(int j=i; j<=m; ++j)
    62                 {
    63                     int x=e[j].u;
    64                     int y=e[j].v;
    65                     int z=e[j].w;
    66                     int fx=finds(x);
    67                     int fy=finds(y);
    68                     if(fx!=fy)
    69                     {
    70                         fa[fx]=fy;
    71                         ++ans;
    72                     }
    73                     if(ans==n-1)
    74                     {
    75                         //if(i!=1)
    76                         //minn=min(minn,z-e[i-1].w);
    77                         //else
    78                         minn=min(minn,z-e[i].w);
    79                         //printf("%d %d %d\n",i,z,e[i-1].w);
    80                     }
    81                 }
    82                 if(ans!=n-1 && i==1)
    83                 {
    84                     flag=1;
    85                     break;
    86                 }
    87             }
    88         }
    89         if(!flag)
    90         printf("%d\n",minn);
    91         else printf("-1\n");
    92     }
    93     return 0;
    94 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11507640.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif