UVA 11354 LCA+最小生成树
来源：程序员人生 发布时间：2016-07-04 11:46:44 阅读次数：2233次
点击打开链接
题意：给1个无向图，然后有Q次询问U V，问的是U到V的所有路径中的最小值最大
思路：U到V的路径最小值最大，则这条边肯定是最小生成树上的边，那末我们可以先将所有的最小生成树上的边全都找出来，然后现在是1个树，然后跑1边LCA，对现在询问的U到V，只要找到它们的最近公共先人，然后两个点向上找到它，比较路径中的最大值便可 PS:这么暴力找跑得有点慢
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=50010;
bool vis[maxn];
int n,m,k;
int L[maxn*2],E[maxn*2],H[maxn],dis[maxn],dp[2*maxn][20],num[maxn],sum[maxn],head[maxn],kkk,pre[maxn];
struct node{
int to,next,cost;
}EE[maxn*4];
void add_edge(int u,int v,int cost){
EE[kkk].to=v;EE[kkk].cost=cost;EE[kkk].next=head[u];head[u]=kkk++;
}
void dfs(int t,int deep){
k++;E[k]=t;L[k]=deep;H[t]=k;
for(int i=head[t];i!=⑴;i=EE[i].next){
int tt=EE[i].to;
if(!vis[tt]){
vis[tt]=1;pre[tt]=t;
dis[tt]=dis[t]+EE[i].cost;
dfs(tt,deep+1);
k++;E[k]=t;L[k]=deep;
}
}
}
void RMQ_init(){
for(int i=1;i<=2*n⑴;i++) dp[i][0]=i;
for(int i=1;(1<<i)<=2*n⑴;i++){
for(int j=1;j+(1<<i)⑴<=2*n⑴;j++){
if(L[dp[j][i⑴]]<L[dp[j+(1<<(i⑴))][i⑴]]) dp[j][i]=dp[j][i⑴];
else dp[j][i]=dp[j+(1<<(i⑴))][i⑴];
}
}
}
int RMQ(int le,int ri){
le=H[le];ri=H[ri];
if(le>ri) swap(le,ri);
int kk=0;
while((1<<(kk+1))<=ri-le+1) kk++;
if(L[dp[le][kk]]<L[dp[ri-(1<<kk)+1][kk]]) return E[dp[le][kk]];
else return E[dp[ri-(1<<kk)+1][kk]];
}
struct edge1{
int u,v,cost;
};
edge1 es[maxn*4];
bool cmp(const edge1 &a,const edge1 &b){
return a.cost<b.cost;
}
int V,EEE,f[maxn];
int find1(int x){
if(x!=f[x]) f[x]=find1(f[x]);
return f[x];
}
void unite(int a,int b){
int aa=find1(a);
int bb=find1(b);
if(aa==bb) return ;
f[aa]=bb;
}
void kruskal(){
sort(es,es+EEE,cmp);
for(int i=0;i<=V;i++) f[i]=i;
for(int i=0;i<EEE;i++){
edge1 e=es[i];
if(find1(e.u)!=find1(e.v)){
unite(e.u,e.v);
add_edge(e.u,e.v,e.cost);
add_edge(e.v,e.u,e.cost);
}
}
}
int main(){
int q,u,v,cost,cas=0;
while(scanf("%d%d",&n,&m)!=⑴){
EEE=m;V=n;
if(cas++) printf("\n");
for(int i=0;i<=n;i++) vis[i]=0,dis[i]=0;
for(int i=0;i<=n;i++) head[i]=⑴;
for(int i=0;i<m;i++) scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);
kruskal();
kkk=0;k=0;vis[1]=1;dfs(1,1);RMQ_init();
scanf("%d",&q);
while(q--){
scanf("%d%d",&u,&v);
int ans=RMQ(u,v);
int min1=0;
while(u!=ans){
min1=max(min1,dis[u]-dis[pre[u]]);
u=pre[u];
}
while(v!=ans){
min1=max(min1,dis[v]-dis[pre[v]]);
v=pre[v];
}
printf("%d\n",min1);
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
