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

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

题目链接：

Out of Hay

题目基础：最小生成树

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

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

思路：

题目大意：

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

题解：

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

坑：

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

还有，起点是0，不是1

Prim解法代码：

include

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;