图论基础知识(三)

此内容包括图论最短路径的五道题目(比较经典，这里只举出其中一例)。
不得不说，csdn里面总是有很多大神善于总结，从他们那边了解到了具体准备ACM应该从哪些层面准备，以及相应的准备方法。图论中最长见到的就是最短路径的题目了，因此主要的题目我也在这里阐明.

题目列表

题目主要取自于poj上的题目，详情可以参考这位大佬的博客链接
https://blog.csdn.net/u013752495/article/details/49009947
对应poj题目

poj1125 Stockbroker Grapevine
poj3615 Cow Hurdles
poj1847 Tram
poj1502 MPI Maelstrom
poj1860 Currency Exchange

我以第二个为例子说明一下
题目如下:

Description

Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向路径，第i条路经是从站台Si开始，到站台Ei，其中最高的栏的高度为Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑，奶牛们都要跨栏。奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N)，表示奶牛必须从站台Ai跑到站台Bi，可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi，使路径上最高的栏的高度最小。你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

Input

行 1: 两个整数 N, M, T
行2..M+1: 行 i+1 包含三个整数 Si , Ei , Hi 行 M+2..M+T+1: 行 i+M+1 包含两个整数，表示任务i的起始站台和目标站台: Ai , Bi

Output

行 1..T: 行 i 为一个整数，表示任务i路径上最高的栏的高度的最小值。如果无法到达，输出 -1。

Sample Input

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

Sample Output

4
8
-1

首先附上代码，仅供参考：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,t;
int a[305][305]; 
int main(){
   #ifdef LOCAL
   /*freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);*/
   #endif
   scanf("%d%d%d",&n,&m,&t);
   memset(a,0x3f,sizeof a);
   for(int i=0,x,y,z;i<m;i++){
       scanf("%d%d%d",&x,&y,&z);
       a[x][y]=min(a[x][y],z);
   }
   for(int k=1;k<=n;k++){
       for(int i=1;i<=n;i++){
           for(int j=1;j<=n;j++){
               a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
           }
       }
   }
   for(int i=0,x,y;i<t;i++){
       scanf("%d%d",&x,&y);
       printf("%d\n",a[x][y]==0x3f3f3f3f?-1:a[x][y]);
   }
   return 0;
}

题解

其实本体就是folyd算法的变形，从数学来说，就是例题的变式一样，主要就是给你一个有向图,然后对于特定的点A与B,要你求出A到B之间所有可行路径的单段路距离最大值的最小值.
剥除floyd的外壳，本题d[i][j]表示的是从i到j的所有路径中单段路距离最大值的最小值。所以其实本题还是依据动态规划的思想来做的，这里
d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
当不同类d[i][k]和d[k][j]合并的时候，取得是max(最大值，因为我们要求i到j这段路内的最大值)。然后当同类路径值(即两个d[i][j]可行值)选优时，取得是最小值(因为我们要求所有i到j路径目的值中的最小值)。

从上题中我们看到了，凡是最大中最小值的，亦或是最小值中的最大值，都可以使用DP的思想解决，DP也是这段时间必须攻克的地方。