poj 1797 ——

思路：

这道题我们可以采用类似于求最短路径的方法，用一种新的“松弛操作”去取代原本的方法。

我们可以记录d[u]为运送货物到点j时最大可载重量。那么对于一条边(x,y),我们有d[y]=max(d[y],min(d[x],v(x,y))).

因此，我们可以直接仿照spfa/dijkstra算法求最短路径的方法解决这道题目。

这道题实际上也是可以通过最小生成树方法解决，不过这里需要求的是最大生成树。

我们可以得出对于所求的路径，实际上就是最大生成树中两点的路径。

但这里我们只来说一下用最短路的方法。

代码：

#include 
         
            #include 
          
             #include 
           
              #include 
            
               #include 
             
                #include 
              
                #include 
               
                 #include 
                
                  #include 
                 
                   using namespace std; const int INF=10000000; int n,m; int dis[1005]; bool vis[1005]; int map[1005][1005]; int dij() { memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++) dis[i]=map[1][i]; vis[1]=true; for(int i=1;i<=n;i++) { int x,m=0; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]>m) m=dis[x=j]; vis[x]=true; if(m==0) break; for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]