题目描述

A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：

输入文件名为 truck.in。

输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道

路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。

 

输出格式：

 

输出文件名为 truck.out。

输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货

车不能到达目的地，输出-1。

 

输入输出样例

输入样例#1：

4 31 2 42 3 33 1 131 31 41 3

输出样例#1：

3-13

说明

对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；

对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；

对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。

一些想法

一句话题意：n个点m条边的无向带权图，求某两点之间最短路径上权值最小的那条边的权值。

货车要运尽可能多的货，就应该走有尽可能大承受力的道路，因此，货车一定在这些点的最大生成树上运货，当然，可能会有些点并不连通，所以也可能是最大生成树的森林。那么查询这两个点路径上权值最小的那条边的权值我们使用LCA，然而我并不会tarjan的LCA的离线做法，所以就用倍增吧。

首先对于输入的边权值排序，然后使用Kruskal求得最大生成树森林。这里我们用并查集维护点与点之间是否在一棵树上。对于求LCA我们使用一个Up数组，Up[i][j]表示i节点的向上跳2^j步到达的点。那么 Up[i][0]就是i节点的父节点，  并且Up[i][j]=Up[Up[i][j-1]][j-1] ，即i节点向上跳2^j等同于i节点向上跳2^j-1后再跳2^j-1，因为2^j=2^(j-1)+2^(j-1)。其次我们还需要一个数组Min，Min[i][j]表示i节点到Up[i][j] 路径上最小的边权值，那么Min[i][j]=min(Min[i][j-1],Min[Up[i][j-1]][j-1]),即i节点到Up[i][j]路径上最小边权值等于节点i到Up[i][j-1]路径上的最小边权值以及节点Up[i] [j-1]到Up[Up[i][j-1][j-1]路径上的最小边权值二者的最小值。我们需要先预处理这两个数组，然后使用倍增求答案，但是在倍增前我们必须保证两个节点在树中的深度是相同的，所以我们还需要一个数组rank记录节点在树中的深度，一遍dfs求得。然后我们对于深度不等的节点，调整较深节点，我们从大到小枚举j，如果它向上跳2^j的深度还是深于另一个节点，就跳，否则不跳，可以确定的是，最终一定会跳到同一深度，在跳的同时我们记录一下在这路径上的最小边权值，同一深度后进行同步倍增，一直到它们的祖先节点是他们的公共祖先，停止倍增，向上同时上提，同时记录在向上倍增的路径边权最小值。

简述：kruskal求最大生成树，并查集维护同一棵树，倍增求LCA得最短路径同时记录路径边权最小值。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define debug(x) cerr<<#x<<'='<
           
            <
            
             y.w;}int Find(int x){//并查集 int k,j,r; r=x; while (r!=father[r]) r=father[r]; k=x; while (k!=r){ j=father[x]; father[x]=r; k=j; } return r;}void Unite(int x,int y){//并查集 x=Find(x); y=Find(y); if(x==y) return; else father[x]=y;}void Add(int x,int y,int z){//对最大生成树边的处理 k++; weight[k]=z; terminal[k]=y; nxt[k]=first[x]; first[x]=k;} void Kruskal(void){//最大生成树 for (int i=1;i<=m;i++){ if (Find(sylvia[i].s)!=Find(sylvia[i].t)){ Unite(Find(sylvia[i].s),Find(sylvia[i].t)); Add(sylvia[i].s,sylvia[i].t,sylvia[i].w); Add(sylvia[i].t,sylvia[i].s,sylvia[i].w); } }}void DFS(int u,int h){//预处理出Min[i][0]和Up[i][0] int temp; rank[u]=h; vis[u]=true; for (temp=first[u];temp!=-1;temp=nxt[temp]){ if (!vis[terminal[temp]]){ Up[terminal[temp]][0]=u; Min[terminal[temp]][0]=weight[temp]; DFS(terminal[temp],h+1); } }}int LCA(int x,int y){//求LCA int ans=INF; if (rank[x]
             
              =0;i--){ if(rank[Up[x][i]]>=rank[y]){ ans=min(ans,Min[x][i]); x=Up[x][i]; if (rank[x]==rank[y]) break; } } if (x==y) return ans; for (int i=22;i>=0;i--){ if (Up[x][i]!=Up[y][i]){ ans=min(ans,min(Min[x][i],Min[y][i])); x=Up[x][i]; y=Up[y][i]; } } ans=min(ans,min(Min[x][0],Min[y][0])); return ans;} int main (){ memset(vis,false,sizeof(vis)); memset(first,-1,sizeof(first)); memset(Min,0x7f,sizeof(Min)); memset(rank,0,sizeof(rank)); memset(Up,0,sizeof(Up)); cin>>n>>m; for (int i=1;i<=m;i++) scanf("%d%d%d",&sylvia[i].s,&sylvia[i].t,&sylvia[i].w); sort(sylvia+1,sylvia+m+1,cmp);//按边权值从大到小排序 for (int i=0;i
              
               >q; for (int i=1;i<=q;i++){ scanf("%d%d",&x,&y); if (Find(x)!=Find(y)) { printf("-1\n"); continue; } else printf("%d\n",LCA(x,y)); } return 0;}
              
             
            
           
          
         
        
       
      
     

 

---

 

 

春

春水初生

春林初盛

春风十里，不如你

 

---

 

Sylvia

二零一七年八月七日