浙大数据结构：07-图4 哈利·波特的考试

这道题使用Floyd算法，初次接触该算法会比较难理解，需要去网上查找相关资料多学习一下再来思考这道题，否则这道题理解起来很吃力。

1、条件准备        

 #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'

 先存图，用w二维数组来存，输入两条边和权重，存到数组中

std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<vector<int>> w(n+3,vector<int>(n+3,20000));rep(i,1,m){int a,b,c;cin>>a>>b>>c;w[a][b]=w[b][a]=c;}

2、bfs算法

因为是无向图，所以从任意起点出发如果没走完所有点，那么这个图不是连通的输出0.

if(bfs(w,n)!=n){cout<<'0';return 0;}

这里还是用数组模拟队列，从结点1开始遍历。

返回遍历的结点数量

int bfs(vector<vector<int>>& w,int n)
{int q[105];int tt=-1,hh=0;q[++tt]=1;int visit[105]={0};visit[1]=1;while(hh<=tt){int cur=q[hh++];rep(i,1,n){if(!visit[i]&&w[cur][i]!=20000){q[++tt]=i;visit[i]=1;}}}return tt+1;
}

3、floyd算法

其实该算法是一种动态规划，dp[k][i][j]的含义是从i到j的最短路经过的最大结点为k。

• 不选 k，那么中间节点的编号都 ≤k−1，即 dp(k,i,j)=dp(k−1,i,j)。
• 选 k，问题分解成从 i 到 k 的最短路，以及从 k 到 j 的最短路。由于这两条最短路的中间节点都不包含 k，所以中间节点的编号都 ≤k−1，故得到 dp(k,i,j)=dp(k−1,i,k)+dp(k−1,k,j)。

因为结点从1开始，我们把k为0的时候存上图，最后就能让上层扫到了 

  vector<vector<vector<int>>> dp(n+3,vector<vector<int>>(n+3,vector<int>(n+3,0)));dp[0]=w;rep(k,1,n)rep(i,1,n)rep(j,1,n)dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);

4、找最远距离最短输出

ans为某点到所有结点的最远距离。node为结点编号。

遍历dp最顶层，存的即为任意两点之间最短距离。

循环遍历，sum存该节点到其它结点的最远距离，注意i!=j

sum如果小于ans则更新答案

int ans=20000,node;rep(i,1,n){int sum=0;rep(j,1,n){if(j!=i)sum=max(sum,dp[n][i][j]);}if(sum<ans){ans=sum;node=i;}}cout<<node<<' '<<ans;

5、总结

这道题的难点在于floyd算法，建议初学者去查找一些类似题对该算法的详细解释再来做本题。

不过这个算法开始还是比较难理解的，需要反复多次想才能真正明白。

完整代码如下：

  #include <bits/stdc++.h>#define rep(i, l, r) for (int i = l; i <= r; i++)using namespace std;#define endl '\n'int bfs(vector<vector<int>>& w,int n)
{int q[105];int tt=-1,hh=0;q[++tt]=1;int visit[105]={0};visit[1]=1;while(hh<=tt){int cur=q[hh++];rep(i,1,n){if(!visit[i]&&w[cur][i]!=20000){q[++tt]=i;visit[i]=1;}}}return tt+1;
}int main(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<vector<int>> w(n+3,vector<int>(n+3,20000));rep(i,1,m){int a,b,c;cin>>a>>b>>c;w[a][b]=w[b][a]=c;}if(bfs(w,n)!=n){cout<<'0';return 0;}vector<vector<vector<int>>> dp(n+3,vector<vector<int>>(n+3,vector<int>(n+3,0)));dp[0]=w;rep(k,1,n)rep(i,1,n)rep(j,1,n)dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j]);int ans=20000,node;rep(i,1,n){int sum=0;rep(j,1,n){if(j!=i)sum=max(sum,dp[n][i][j]);}if(sum<ans){ans=sum;node=i;}}cout<<node<<' '<<ans;return 0;}