最小生成树(Kruskal)HDU 1863-畅通工程

蔚落 2022-05-15 06:44 187阅读 0赞

*  # 最小生成树(Kruskal)HDU 1863-畅通工程 #

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

*  ## 题目链接： ##

### [畅通工程][Link 1] ###

*  ## 题目基础： ##

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

*  ## 思路： ##

### 题目大意： ###

中文题目略

### 题解： ###

Kruskal水题，有个概念，***如果M个村庄能够连通，并且是在并查集下连通，需满足道路数Road\_Num=M-1***

所以在题目中，如果合并的道路小于M-1，是不能将M个村庄连通的

*  ## 代码： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAX_SIZE 105
    struct Road
    {
        int Begin;
        int End;
        int Price;
        bool operator<(Road b)const
        {
            return this->Price<b.Price;
        }
    };
    
    Road Road_List[MAX_SIZE];
    int Village[MAX_SIZE];
    int Rank[MAX_SIZE];
    
    void Init(int n)
    {
        for(int i=1;i<=n;i++)
        {
            Rank[i]=0;
            Village[i]=-1;
        }
    }
    
    int Find(int x)
    {
        int root=x;
        while(Village[root]!=-1)
            root=Village[root];
        while(x!=root)
        {
            int temp=Village[x];
            Village[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])
            Village[a_root]=b_root;
        else
        {
            Village[b_root]=a_root;
            if(Rank[a_root]==Rank[b_root])
                Rank[a_root]++;
        }
        return 1;
    }
    
    int Kruskal(int n,int m)   //n为给定道路数，m为村庄数
    {
        int Road_Num=0;
        int Min_Cost=0;
        sort(Road_List+1,Road_List+n+1);
        for(int i=1;i<=n&&Road_Num!=m-1;i++)
        {
            if(Combine(Road_List[i].Begin,Road_List[i].End))
            {
                Min_Cost+=Road_List[i].Price;
                Road_Num++;
            }
        }
        if(Road_Num<m-1)   //不满足所有村庄连通
            return -1;
        else
            return Min_Cost;
    }
    
    int main()
    {
        int N,M;
        while(cin>>N>>M&&N)
        {
            Init(M);
            for(int i=1;i<=N;i++)
                cin>>Road_List[i].Begin>>Road_List[i].End>>Road_List[i].Price;
            int Res=Kruskal(N,M);
            if(Res==-1)
                cout<<"?"<<endl;
            else
                cout<<Res<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1863
[-Kruskal]: https://blog.csdn.net/SZU_Crayon/article/details/82078700