欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

07-图4 哈利·波特的考试 (25分)

程序员文章站 2024-01-19 15:36:16
...

07-图4 哈利·波特的考试 (25分)
07-图4 哈利·波特的考试 (25分)解题思路:根据题目的意思就是找任意两个点之间的最短路径,也就是多源最短路径的算法,即Floyd算法(弗洛伊德算法),里面要注意的细节是,因为顶点是从1开始,所以在生成邻接矩阵的时候,我这里采用的是从下标1开始初始化为INFINITY

#include<iostream>
#define MaxVertexNum 101
#define INFINITY 65535
using namespace std;
//定义图的存储结构-邻接矩阵
typedef struct ENode
{
    int V1,V2;
    int Weight;
} *Edge;
typedef struct GNode
{
    int Nv,Ne;
    int G[MaxVertexNum][MaxVertexNum];
}* MGraph;

MGraph BuildGraph();
void InsertEdge(MGraph Graph, Edge E);
MGraph CreateGraph(int VertexNum);
void FindAnimal(MGraph Graph);
void Floyd(MGraph Graph,int Dist[][MaxVertexNum]);
int FindMaxDist(int Dist[][MaxVertexNum],int i,int VertexNum);

int main()
{
    MGraph Graph;
    Graph = BuildGraph();
    FindAnimal(Graph);
    return 0;
}
MGraph BuildGraph()
{
    MGraph Graph;
    int VertexNum,EdgeNum;
    cin >> VertexNum >> EdgeNum;
    Graph = CreateGraph(VertexNum);
    Graph->Ne = EdgeNum;
    int i;
    if(EdgeNum!=0)
    {
        Edge E = new ENode;
        for(i = 0; i<Graph->Ne;i++)
        {
            cin >> E->V1 >>E->V2>>E->Weight;
            InsertEdge(Graph,E);
        }
    }
    return Graph;
}
void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2]=E->Weight;
    Graph->G[E->V2][E->V1]=E->Weight;
}
MGraph CreateGraph(int VertexNum)
{
    MGraph Graph;
    Graph = new GNode;
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    int i,j;
    for(i = 1;i<=Graph->Nv;i++)
     for(j = 1;j<=Graph->Nv;j++)
        Graph->G[i][j] = INFINITY;
    return Graph;
}
void FindAnimal(MGraph Graph)
{
    int Dist[MaxVertexNum][MaxVertexNum];
    int MinDist,MaxDist,i,Animal=0;
    Floyd(Graph,Dist);
    MinDist = INFINITY;//不一定非要是INFINITY,这里只是想要存储一个最大的路径
    for(i=1;i<=Graph->Nv;i++)
    {
        MaxDist = FindMaxDist(Dist,i,Graph->Nv);
        if(MaxDist==INFINITY)//如果有没有连通的点,也就是只带一只动物变不到任意那个动物
        {
            cout<<"0";
            return;
        }
        if(MinDist>MaxDist)
        {
            MinDist = MaxDist;
            Animal = i;
        }
    }
    cout<<Animal<<" "<<MinDist;
}
void Floyd(MGraph Graph,int Dist[][MaxVertexNum])
{
    int k,i,j;//K表示要比较是第几个,k的最大值也是图的结点数,i和j用来for循环
    for(i = 1;i<=Graph->Nv;i++)
        for(j = 1; j<=Graph->Nv;j++)
            Dist[i][j] = Graph->G[i][j];
    for(k = 1;k<=Graph->Nv;k++)
        for(i=1;i<=Graph->Nv;i++)
            for(j=1;j<=Graph->Nv;j++)
            {
                if(Dist[i][j]>Dist[i][k]+Dist[k][j])
                    Dist[i][j]=Dist[i][k]+Dist[k][j];//可以不用加负圈值的判断,因为题目都给的正整数
            }
}
int FindMaxDist(int Dist[][MaxVertexNum],int i,int VertexNum)
{
    int MaxDist;
    int j;
    MaxDist = 0;
    for(j = 1;j<=VertexNum;j++)
        if(MaxDist<Dist[i][j]&&i!=j)//去掉对角线,因为对角线永远是正无穷,永远最大
            MaxDist = Dist[i][j];
    return MaxDist;
}