最小生成树(Kruskal)POJ 1258 Agri-Net

朱雀 2022-05-15 06:43 182阅读 0赞

*  # 最小生成树(Kruskal)POJ 1258 Agri-Net #

--------------------

*  ## 题目链接： ##

### [Agri-Net][] ###

*  ## 题目基础： ##

### [最小生成树-Kruskal(克鲁斯卡尔)算法][-Kruskal] ###

*  ## 思路： ##

### 题目大意： ###

有N个村庄，输入每个村庄到编号为1~N的距离，每个村落都需要网络覆盖，问网线的最短长度

### 题解： ###

最小生成树的裸题，按模板打

说个优化吧，样例给的是一个矩阵，但很容易想到，1到3的距离和3到1的距离是没有区别的，所有其实整个矩阵，***用到的数据就只有上三角，也就是 i>j 的部分***

*  ## 代码： ##

#include <iostream>
    #include<algorithm>
    using namespace std;
    #define MAX_SiZE 5000
    
    struct Connect
    {
        int Begin;
        int End;
        int Length;
        bool operator<(Connect b)const
        {
            return this->Length<b.Length;
        }
    };
    Connect Connect_List[MAX_SiZE];
    int Farms[MAX_SiZE];
    int Rank[MAX_SiZE];
    
    void Init(int n)
    {
        for(int i=1;i<=n;i++)
        {
            Rank[i]=0;
            Farms[i]=-1;
        }
    }
    
    int Find(int x)
    {
        int root=x;
        while(Farms[root]!=-1)
            root=Farms[root];
        while(x!=root)
        {
            int temp=Farms[x];
            Farms[x]=root;
            x=temp;
        }
        return root;
    }
    
    int Combine(int a,int b)
    {
        int a_root=Find(a);
        int b_root=Find(b);
        if(a_root==b_root)
            return 0;
        if(Rank[a_root]<Rank[b_root])
            Farms[b_root]=a_root;
        else
        {
            Farms[a_root]=b_root;
            if(Rank[a_root]==Rank[b_root])
                Rank[a_root]++;
        }
        return 1;
    }
    
    int Kruskal(int N,int M)   //N是村庄数量，M为两个村庄间距离（边）的总数量
    {
        int Connect_Num=0;
        int Min_Length=0;
        sort(Connect_List+1,Connect_List+M+1);
        for(int i=1;i<=M&&Connect_Num!=N-1;i++)
        {
            if(Combine(Connect_List[i].Begin,Connect_List[i].End))
            {
                Connect_Num++;
                Min_Length+=Connect_List[i].Length;
            }
        }
        if(Connect_Num<N-1)
            return -1;
        return Min_Length;
    }
    
    int main()
    {
        int N;
        while(cin>>N)
        {
            int M=0;
            int Len;
            for(int i=1;i<=N;i++)
            {
                for(int j=1;j<=N;j++)
                {
                    cin>>Len;
                    if(j>i)
                    {
                        Connect_List[++M].Begin=i;
                        Connect_List[M].End=j;
                        Connect_List[M].Length=Len;
                    }
                }
            }
            Init(M);
            int Res=Kruskal(N,M);
            cout<<Res<<endl;
        }
        return 0;
    }

[Agri-Net]: http://poj.org/problem?id=1258
[-Kruskal]: https://blog.csdn.net/SZU_Crayon/article/details/82078700