货车运输
【题目描述】
A国有n座城市，编号从1到n，城市之间有m条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有q辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
【输入输出格式】
- 输入格式
输入文件第一行有两个用一个空格隔开的整数n，m，表示A国有n座城市和m条道路。接下来m行每行3个整数x、y、z，每两个整数之间用一个空格隔开，表示从x号城市到y号城市有一条限重为z的道路。注意：x不等于y，两座城市之间可能有多条道路。接下来一行有一个整数q，表示有q辆货车需要运货。接下来q行，每行两个整数x、y，之间用一个空格隔开，表示一辆货车需要从x城市运输货物到y城市，注意：x不等于y。
- 输出格式
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
·输入样例：
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
·输出样例：
3 -1 3
思路：
因为要运输最多的货物，所以在全部边里需要尽量长的边，所以要一棵最大生成树。
因为要求两点之间的最短路，数据量很大，又是树上的两点的距离，所以运用倍增。
盲点：
１．如何求最大生成树？－－仿照求最小生成树ｋｒｕｓｋａｌ的算法，结合并查集。
２．如何建最大生成树？－－首先把题目中的边读取进来，用结构体保存，记录起点、终点、边权。接着求出最大生成树时，边求边建树。
３．如何求树上两点之间的最短距离？－－运用倍增，记录一个ｗ数组ｗ［ｉ］［２０］，表示ｉ向上跳２＾ｊ步，初始化为ｉｎｆ，更新到他时，首先ｅｄｇｅ［ｆａ］．ｗ，转移方程是 w[j][i]=min(w[j][i-1], w[fa[j][i-1]][i-1])。
代码：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=50000+100; const int MAXN=100000+100; int rd(){ int s=0; char c=getchar(); while(c>'9'||c<'0')c=getchar(); while(c<='9'&&c>='0'){s=s*10+c-'0';c=getchar();} return s; } //强调一下数组的问题哈，最大生成树用的边要100000多，后面倍增从0-20，是21个位置 int n,m,head[maxn],tot,q,w[maxn][21],deep[maxn],fa[maxn][21],ff[maxn]; bool v[maxn]; //题目所给信息的图，假的图 struct eeee{ int f,t,w; }edge1[MAXN]; //用最大生成树建的图，真的图 struct EDGE{ int next,to,w; }edge2[maxn]; void add(int x,int y,int z) { edge2[++tot].next=head[x]; edge2[tot].to=y; edge2[tot].w=z; head[x]=tot; } //并查集 int find(int x) { if(ff[x]==x)return x; ff[x]=find(ff[x]); return ff[x]; }//这里并查集的递归是需要理解记忆的，必须要边搜边保存 void unionn(int x,int y) { ff[x]=y; } bool cmp(eeee a,eeee b) { return a.w>b.w; } //最大生成树 void kruskal() { sort(edge1+1,edge1+1+m,cmp); for(int i=1;i<=n;i++)ff[i]=i; for(int i=1;i<=m;i++) { int x=find(edge1[i].f),y=find(edge1[i].t); if(x!=y) { unionn(x,y); add(edge1[i].f,edge1[i].t,edge1[i].w); add(edge1[i].t,edge1[i].f,edge1[i].w); } } } //介入问题去求两点路径间的最小值 //初始化deep、w、v数组 void update(int u) { v[u]=1; for(int i=head[u];i;i=edge2[i].next) { int to=edge2[i].to; if(v[to])continue; deep[to]=deep[u]+1; fa[to][0]=u; w[to][0]=edge2[i].w; update(to); } } //倍增初始化fa、w数组，w即j节点跳2^i个节点经历的线段中最短的 void initial() { for(int i=1;i<=20;i++) { for(int j=1;j<=n;j++) { fa[j][i]=fa[fa[j][i-1]][i-1]; w[j][i]=min(w[fa[j][i-1]][i-1],w[j][i-1]); } } } //LCA 模板 求答案 int query(int x,int y) { if(find(x)!=find(y))return -1; int ans=0x3f3f3f3f; if(deep[x]<deep[y])swap(x,y);//x为下面的 //让x跳至与y同一层 for(int i=20;i>=0;i--) { if(deep[fa[x][i]]>=deep[y]){ ans=min(ans,w[x][i]); x=fa[x][i]; } } if(x==y)return ans;//已经找到lca for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { ans=min(ans,min(w[x][i],w[y][i])); x=fa[x][i],y=fa[y][i]; } } ans=min(ans,min(w[x][0],w[y][0]));// 现在的x/y向上跳一步就是他们的爸爸啦 return ans; } int main() { n=rd(),m=rd(); for(int i=1;i<=m;i++) { int x,y,z; x=rd(),y=rd(),z=rd(); edge1[i].f=x,edge1[i].t=y,edge1[i].w=z; } kruskal(); //为了防止有不连通的点，需要每个都遍历 for(int i=1;i<=n;i++) { if(!v[i])//这里又是一个槽点，调试半天... 这个意思是v[i]为0 { deep[i]=1; update(i); fa[i][0]=i; w[i][0]=0x3f3f3f3f; } } //解决问题 q=rd(); initial(); for(int i=1;i<=q;i++) { int x=rd(),y=rd(); int ans=query(x,y); printf("%d ",ans); } return 0; }