POJ 2263 Heavy Cargo（ZOJ 1952） - c++编程基础

最短路变形或最大生成树变形。

问目标两地之间能通过的小重量。

用最短路把初始赋为INF，其他为0.然后找 dis[v]=min(dis[u], d);

生成树就是把最大生成树找出来，直到出发和终点能沟通的时候，最小的边就是。

Kruskal：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; int fa[201]; map
             
              city; struct lx { int u,v,len; }l[19901]; int father(int x) { if(x!=fa[x]) return fa[x]=father(fa[x]); } bool cmp(lx a, lx b) { return a.len>b.len; } int main() { int nn=1; while(scanf("%d%d",&n,&m),n||m) { for(int i=0;i<=n;i++) fa[i]=i; city.clear(); char a[31],b[31]; int len,u,v,cot=0; for(int i=0;i