07-图4 哈利·波特的考试 (25分)
程序员文章站
2024-01-19 15:36:16
...
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;
}
推荐阅读