Poj 3522 最长边与最短边差值最小的生成树

题意：

让你求一颗生成树，使得最长边和最短边长度差值最小。

思路：

额！！！感觉这个思路会超时，但是ac了，暂时没什么别的好思路，那么就先说下这个思路，大牛要是有好的思路希望能在下面留言，相互学习，我的方法是先把所有的边都按长度排序，然后枚举没一颗生成树，这样枚举能得到正确答案的原因是，如果是求最小的差值，那么最终的答案一定是在sort之后的连续的以段，我们只要枚举每一段就行了，但是这样的时间复杂度是O(M^2)的，如果碰到奇葩数据估计一组可能跑到将近1s这样就T了，呵呵。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define N 110

using namespace std;

typedef struct

{

int a ,b ,c;

}EDGE;

EDGE edge[N*N/2];

int mer[N];

int finds(int x)

{

return x == mer[x] ? x : mer[x] = finds(mer[x]);

}

bool camp(EDGE a ,EDGE b)

{

return a.c < b.c;

}

int main ()

{

    int n ,m ,i ,j ,Ans;

    while(~scanf("%d %d" ,&n ,&m) && n + m)

    {

        Ans = -1;

        for(i = 1 ;i <= m ;i ++)

        scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);

        sort(edge + 1 ,edge + m + 1 ,camp);

        for(i = 1 ;i <= m ;i ++)

        {

            for(j = 1 ;j <= n ;j ++)

            mer[j] = j;

            int sss = 0;

            for(j = i ;j <= m ;j ++)

            {

               int xx = finds(edge[j].a);

               int yy = finds(edge[j].b);

               if(xx != yy) sss++ ,mer[xx] = yy;

               if(sss == n - 1)

               {

                  if(Ans == -1 || Ans > edge[j].c - edge[i].c)

                  Ans = edge[j].c - edge[i].c;

                  break;

               }

            }

        }

        printf("%d\n" ,Ans);

    }

    return 0;

}

巴特西

Poj 3522 最长边与最短边差值最小的生成树

最新文章

热门文章