DP（仿照Floyd）

题意：一个无向图，然后多个查询，查询是起点和终点s和t，s到t可能有多条路径，那么每条路径都会有一条权值最大的边，在所有的最大边中找一个最小的，如果s到t之间不连通，那么输出no path

想了很久，大概有两个小时的样子…………然后看了一下数据，刚好最多有100个点，最多10000个查询，那么就给了一个很大的启发，会不会有一个算法会好像dij一样，运行一次能得到做个答案，或者一个算法好像floyd一样，运行一次可以知道所有答案，出于数据的特殊性，我更倾向于往floyd的方向想。

floyd的本质是DP，其实这个问题也很容易发现就是个DP，状态转移方程为

 

max=MAX{ d[i][k] , d[k][j]} 

d[i][j]=MIN{d[i][j] , max}

 

DP思想很容易想到，从i到j，如果经过k点，并且i到k是连通的，k到j是连通的，那么d[i][k]表示i到k的最大值的最小值，d[k][j]表示k到j的最大值的最小值

那么合并两条路径后，最大值的最小值应该是两者中的较大的那个

然后从i到j本身有已有一个最大值的最小值，再比较两者哪个更小，取较小值

当d[i][j]=INF,表示i到j不连通，那么就谈不上什么最大值的最小值

其中初始化d[i][j]=g[i][j]

 

 

#include 
     
      #include 
      
       #define INF 0x3f3f3f3f#define N 110int d[N][N];int n,m,mm;int max(int a ,int b){ return a>b?a:b; }int min(int a, int b){ return a
      
     

 

DP里面的拓展开来可以这样写（方便理解）

if(d[i][k]==INF || d[k][j]==INF)    continue;int m;if(d[i][k]>d[k][j])    m=d[i][k];else     m=d[k][j];if(m