题目描述 Description
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入描述 Input Description
第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道路。
接下来 m 行每行 3 个整数 x、y、z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意：x 不等于 y，两座城市之间可能有多条道路。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意：x 不等于 y。
输出描述 Output Description
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1。
样例输入 Sample Input
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出 Sample Output
3
-1
3
数据范围及提示 Data Size & Hint
对于 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。
直接暴力搜索／／30分
只用一个kruskal／／60分
大概是先用一个最大生成树进行预处理，然后用lac进行在线查询就差不多了／／满分算法。
View Code
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; bool b[10010],visited[10010];//visited每个点只走一遍 int n,m,x,y,z,q,num_edge1,num_edge2,head[10010],deep[10010],father[10010],fa[10010][17],dis[10010][17]; //fa[x][i]:x节点向上跳2^i的节点，fa[x][0]:x节点的父节点；dis[x][i]:节点x向上跳2^i的路径中的最小边权 struct Edge1{ int next,to,dis; }; Edge1 edge1[50010]; struct Edge2{//Kruskal's edge int from,to,value; }; Edge2 edge2[50010]; void add_edge1(int from,int to,int dis)//存最大生成树的图 { edge1[++num_edge1].next=head[from]; edge1[num_edge1].to=to; edge1[num_edge1].dis=dis; head[from]=num_edge1; } void add_edge2(int from,int to,int value)//Kruskal's graph { edge2[++num_edge2].from=from; edge2[num_edge2].to=to; edge2[num_edge2].value=value; } int find(int x) { if (father[x]!=x) return father[x]=find(father[x]); return father[x]; } void unionn(int x,int y) { int xx=find(x); int yy=find(y); if (xx!=yy) father[xx]=yy; } bool comp(Edge2 a,Edge2 b) { return a.value>b.value;//最大生成树 } void dfs(int x)//记忆化搜索，保存每一个点的 deep[] fa[][] dis[][],在后面用到 { visited[x]=1; for (int i=1; i<=16; i++)//初始化 { //2^16=65536>50000 if ((1<<i)>deep[x]) break;//1<<i <=> 2^i fa[x][i]=fa[fa[x][i-1]][i-1];//(2^j-1)+(2^j-1)=2^j dis[x][i]=min(dis[x][i-1],dis[fa[x][i-1]][i-1]);//错误：dis[x][i]=dis[fa[x][i-1]][i-1],应该为较小值啊啊啊 } for (int i=head[x]; i!=0; i=edge1[i].next) {//更新3点 if (!visited[edge1[i].to])//必须没走过，漏了这一点 !! { deep[edge1[i].to]=deep[x]+1; fa[edge1[i].to][0]=x;//存父节点 dis[edge1[i].to][0]=edge1[i].dis;//将dis[j][0]存指向j点的边的权值 dfs(edge1[i].to);//不需要回溯 } } } int lca(int x,int y)//求最近公共祖先 { if (deep[x]<deep[y]) swap(x,y);//交换下标 int d=deep[x]-deep[y];//深度差 for (int i=0; i<=16; i++)//倒？正？ {//从0开始是为了x与y深度一样的情况 if ((1<<i)&d) x=fa[x][i];//使x跳到与y深度相等的地方（d为深度差） } for (int i=16; i>=0; i--)//因为要找最深的公共祖先，所以要倒着找 if (fa[x][i]!=fa[y][i]) {//找祖宗的祖宗 x=fa[x][i];//x和y一起向上跳 y=fa[y][i]; } if (x==y) return x;//x和y重合的情况 return fa[x][0];//如果x和y不重合，x和y就有同一个爹 } int ask(int x,int k)//查询一点到祖先的最小线段 { int minn=0x7fffffff; int d=deep[x]-deep[k];//到祖先的距离 for (int i=16; i >= 0; i--) if ((1<<i)<=d) { minn=min(minn,dis[x][i]); x=fa[x][i];//向上跳 d -= (1 << i); } return minn;} int main() { memset(dis,0x7f/3,sizeof(dis));//不初始化会有大问题 scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) father[i]=i; for (int i=1; i<=m; i++) { scanf("%d%d%d",&x,&y,&z); add_edge2(x,y,z); } sort(edge2+1,edge2+1+m,comp); int k=0; for (int i=1; i<=m; i++) { if (find(edge2[i].from)!=find(edge2[i].to)) { unionn(edge2[i].from,edge2[i].to); add_edge1(edge2[i].from,edge2[i].to,edge2[i].value);//构造最大生成树 add_edge1(edge2[i].to,edge2[i].from,edge2[i].value);//无向图 k++; if (k==n-1) break; } } for (int i=1; i<=n; i++) if (!visited[i]) dfs(i); scanf("%d",&q); for (int i=1; i<=q; i++) { int x,y; scanf("%d%d",&x,&y); if (find(x)!=find(y)) printf("-1 ");//不在一个并查集里面.这种处理方法比==0x7f7f7f7f printf -1 好 else { int grandfather=lca(x,y);//祖先 printf("%d ",min(ask(x,grandfather),ask(y,grandfather))); } } return 0; }