Codevs 3287 货车运输 2013年NOIP全国联赛提高组（带权LCA+并查集+最大生成树）

本文主要是介绍Codevs 3287 货车运输 2013年NOIP全国联赛提高组（带权LCA+并查集+最大生成树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3287 货车运输 2013年NOIP全国联赛提高组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
传送门
题目描述 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。
分类标签 Tags
最小生成树图论大陆地区 NOIP全国联赛提高组 2013年

/*
spfa暴力.
30.
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define MAXN 10001
#define MAXM 100001
using namespace std;
int head[MAXN],dis[MAXN],n,m,cut,k;
struct data{int v,next,x;}e[MAXM];
bool b[MAXN];
queue<int>q;
void add(int u,int v,int z)
{e[++cut].v=v;e[cut].x=z;e[cut].next=head[u];head[u]=cut;
}
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;if(ch==EOF) return -1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void spfa(int s)
{memset(dis,0,sizeof dis);dis[s]=1e9;q.push(s);while(!q.empty()){int u=q.front();q.pop();b[u]=false;for(int i=head[u];i;i=e[i].next){int v=e[i].v;if(dis[v]<min(dis[u],e[i].x)) {dis[v]=min(dis[u],e[i].x);if(!b[v]) b[v]=true,q.push(v);}}}
}
int main()
{int x,y,z;n=read(),m=read();while(m--){x=read(),y=read(),z=read();add(x,y,z),add(y,x,z);}k=read();while(k--){x=read(),y=read();spfa(x);if(!dis[y]) printf("-1\n");else printf("%d\n",dis[y]);}return 0;
}

/*
最大生成树+带权LCA+并查集. 
好题.
每次询问任意两点之间边权最大路径的最小值.
▲读入的时候不能建边.
先kruskal建一棵树并保存数的形态.(prim只能求权值无法保存形态). 
搞的时候维护一个dis[i][j]数组表示从i号节点向上2^j层的到i的最小值.
然后LCA的时候步步取小,步步取小,步步取小.
若deep[i]==0&&i!=1 即改点没有遍历到,return -1. 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 50001
#define D 16
using namespace std;
int head[MAXN],n,m,cut,tot,father[MAXN],fa[MAXN][D+5],deep[MAXN],dis[MAXN][D+5];
struct edge
{int v;int next;int x;
}
e[MAXN<<1];
struct data
{int x,y,z;
}
s[MAXN];
void add(int u,int v,int z)
{tot++;e[tot].x=z;e[tot].v=v;e[tot].next=head[u];head[u]=tot;
}
int ffind(int x)
{if(x!=father[x])  return father[x]=ffind(father[x]);return x;
}
bool cmp(const data &x,const data &y)
{return x.z>y.z;
}
void dfs(int u,int x)
{for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;if(!deep[v]&&v!=1){deep[v]=deep[u]+1;fa[v][0]=u;dis[v][0]=e[i].x;//dis处理.dfs(v,x+1);}}
}
void get_father()
{for(int j=1;j<=D;j++)for(int i=1;i<=n;i++){fa[i][j]=fa[fa[i][j-1]][j-1];dis[i][j]=min(dis[i][j-1],dis[fa[i][j-1]][j-1]);}
}
int get_same(int u,int v)
{for(int i=0;i<=D;i++)if((1<<i)&v) {tot=min(tot,dis[u][i]);u=fa[u][i];}return u;
}
int lca(int u,int v)
{if((u!=1&&!deep[u])||(v!=1&&!deep[v]))  return -1;tot=1e9;if(deep[u]<deep[v]) swap(u,v);u=get_same(u,deep[u]-deep[v]);if(u==v) return tot;for(int i=D;i>=0;i--){if(fa[u][i]!=fa[v][i]){tot=min(tot,dis[u][i]);tot=min(tot,dis[v][i]);u=fa[u][i];v=fa[v][i];}}tot=min(tot,min(dis[u][0],dis[v][0]));return tot;
}
int main()
{memset(head,-1,sizeof(head));memset(dis,127/3,sizeof(dis));int x,y,z,u,v;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(x,y,z);s[i].x=x;s[i].y=y;s[i].z=z;}sort(s+1,s+m+1,cmp);for(int i=1;i<=m;i++){u=s[i].x,v=s[i].y;int r1=ffind(u),r2=ffind(v);if(r1!=r2){add(u,v,s[i].z);add(v,u,s[i].z);father[r2]=r1;cut++;if(cut==n-1) break;}}dfs(1,0);get_father();scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);printf("%d\n",lca(u,v));}return 0;
}