最小生成树(Prim/Kruskal)POJ 2395-Out of Hay

分手后的思念是犯贱 2022-05-15 11:56 115阅读 0赞

*  # 最小生成树(Prim/Kruskal)POJ 2395-Out of Hay #

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

*  ## 题目链接： ##

### [Out of Hay][] ###

*  ## 题目基础：最小生成树 ##

### [最小生成树-Prim(普里姆)算法][-Prim] ###

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

*  ## 思路： ##

### 题目大意： ###

一个人从自己的农场出发，要访问N个农场，一共有M条路径（两个农场之间可能存在多条不等长路径），每个农场有水源，在路上需要消耗水，假设道路长length，需要length的水，这个人尽可能在总路径最短的情况下访问完所有农场，问在路上最多要带多少水

### 题解： ###

其实就是求最小生成树，只不过**需要找出连接路径中最长的一条**

### 坑： ###

在题目大意说了，“两个农场之间可能存在多条不等长路径”，因为我是用prim解，所以**将数据输入邻接矩阵时需要比较下**，kruskal就不必了

还有，起点是0，不是1

*  ## Prim解法代码： ##

#include<iostream>
    #include<algorithm>
    using namespace std;
    using namespace std;
    #define INF 1000000007
    #define MAX_SIZE 10005
    #define Begin 1   //数组开头 1 or 0
    // Path[i]->i have lowest path：Path_low_cost[i]
    int Path[MAX_SIZE]; //结点i的父亲
    int Path_Low_Cost[MAX_SIZE]; //到达结点i的最小值
    int Vis[MAX_SIZE];   //标记已经进入最小树的结点
    int Min_Cost;   //最短路径
    int Res;  //标记最大值
    
    //邻接图
    struct MGrapth
    {
        int Vexs[MAX_SIZE];  //顶点表
        int Arc[MAX_SIZE][MAX_SIZE];  //邻接矩阵
        int Num_Vertext,Num_Edges;  //顶点数，边数
    };
    
    MGrapth Map;
    
    void Init(int N,int M)   //初始化
    {
        Res=-1;
        Min_Cost=0;
        Map.Num_Edges=M;  //边数
        Map.Num_Vertext=N;  //顶点数
        for(int i=0;i<=N;i++)
            for(int j=0;j<=N;j++)
                Map.Arc[i][j]=INF;  //无穷大初始
        for(int i=0;i<=N;i++)
        {
            Path[i]=Path_Low_Cost[i]=INF;
            Map.Vexs[i]=i;
            Vis[i]=false;
        }
    }
    
    void Prim()
    {
        int Min,i,j,k;
        int End=Map.Num_Vertext+1;   //结尾
       
        Path[Begin]=Begin;   //Begin加入生成树
        Path_Low_Cost[Begin]=0;
        Vis[Begin]=true;   //Begin已经加入
    
        for(i=Begin+1;i<End;i++)  
        {
            Path_Low_Cost[i]=Map.Arc[Begin][i];   //首顶点与其他顶点的距离
            Path[i]=Begin;
        }
        for(int i=Begin+1;i<End;i++)
        {
            Min=INF;
            j=Begin+1,k=Begin;
            while(j<End)
            {
                if(!Vis[j]&&Path_Low_Cost[j]<Min)
                {
                    Min=Path_Low_Cost[j];
                    k=j;
                }
                j++;
            }
            Path_Low_Cost[k]=Min;  //保存Path_Low_Cost[k] 到 k 的最短距
            Res=max(Res,Min);  //保存路径最大值
            Vis[k]=true;   //k加入最小生成树
            
            for(j=Begin+1;j<End;j++)
            {
                if(!Vis[j]&&Map.Arc[k][j]<Path_Low_Cost[j])  //如果 j 不在最小生成树内，并且 k到j有更小的路径，记录，更新
                {
                    Path_Low_Cost[j]=Map.Arc[k][j];
                    Path[j]=k;
                }
            }
        }
    }
    
    int main()
    {
        int N,M;
        while(cin>>N>>M)
        {
            Init(N,M);
            for(int i=0;i<M;i++)
            {
                int val,a,b;
                cin>>a>>b>>val;
                if(Map.Arc[a][b]>val)
                    Map.Arc[a][b]=val;
                if(Map.Arc[b][a]>val)
                    Map.Arc[b][a]=val;
            }
            Prim();
            cout<<Res<<endl;
            /*for(int i=Begin;i<=N;i++)
                cout<<Path[i]<<"---"<<i<<"---"<<Path_Low_Cost[i]<<endl;*/
        }
        return 0;
    }

[Out of Hay]: http://poj.org/problem?id=2395
[-Prim]: https://blog.csdn.net/SZU_Crayon/article/details/82182016
[-Kruskal]: https://blog.csdn.net/SZU_Crayon/article/details/82078700