bzoj 3732: Network （最小生成树+LCA）

Description

给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。 图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).

现在有 K个询问 (1 < = K < = 15,000)。 每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Input

第一行： N, M, K。 第2..M+1行: 三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N). 表示X与Y之间有一条长度为D的边。 第M+2..M+K+1行: 每行两个整数A B,表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

Output

 对每个询问，输出最长的边最小值是多少。

Sample Input

Sample Output

HINT

1 <= N <= 15,000 1 <= M <= 30,000 1 <= d_j <= 1,000,000,000 1 <= K <= 15,000 

Source

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100003#define LL long longusing namespace std;int n,m,k,point[N],nxt[N],v[N],len[N],mi[20];int f[N][20],c[N][20],deep[N],tot,fa[N];struct data {	int x,y,z;}e[N];int find(int x){	if (fa[x]==x) return x;	fa[x]=find(fa[x]);	return fa[x];}int cmp(data a,data b){	return a.z<b.z;}void add(int x,int y,int z){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; len[tot]=z;	tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; len[tot]=z;}void dfs(int x,int ff){	deep[x]=deep[ff]+1;	for (int i=1;i<=15;i++) {		if (deep[x]-mi[i]<0) break;		f[x][i]=f[f[x][i-1]][i-1];		c[x][i]=max(c[x][i-1],c[f[x][i-1]][i-1]);	}	for (int i=point[x];i;i=nxt[i]) {		if (v[i]==ff) continue;		f[v[i]][0]=x;		c[v[i]][0]=len[i];		dfs(v[i],x);	}}int lca(int x,int y){	if (deep[x]<deep[y]) swap(x,y);	int k=deep[x]-deep[y];	int ans=0;	for (int i=0;i<=15;i++)	 if (k>>i&1) ans=max(ans,c[x][i]),x=f[x][i];	if (x==y) return ans;	for (int i=15;i>=0;i--) 	if (f[x][i]!=f[y][i]){      ans=max(ans,c[x][i]);      ans=max(ans,c[y][i]);      x=f[x][i];      y=f[y][i];	}	ans=max(ans,c[x][0]);	ans=max(ans,c[y][0]);	return ans;}int main(){	freopen("a.in","r",stdin);	mi[0]=1;	for (int i=1;i<=16;i++) mi[i]=mi[i-1]*2;	scanf("%d%d%d",&n,&m,&k);	for (int i=1;i<=m;i++) {		int x,y,z; scanf("%d%d%d",&x,&y,&z);		e[i].x=x; e[i].y=y; e[i].z=z;	}	sort(e+1,e+m+1,cmp);	for (int i=1;i<=n;i++) fa[i]=i;	int size=0;	for (int i=1;i<=m;i++) {		int r1=find(e[i].x); int r2=find(e[i].y);		if (r1!=r2) {			fa[r2]=r1;			add(e[i].x,e[i].y,e[i].z);			size++;		}		if (size==n-1) break;	}	dfs(1,0);	for (int i=1;i<=k;i++) {		int x,y; scanf("%d%d",&x,&y);		PRintf("%d/n",lca(x,y));	} }