国内最全IT社区平台 联系我们 | 收藏本站
阿里云优惠2流量王
您当前位置:首页 > php开源 > php教程 > UVA 11354 LCA+最小生成树

UVA 11354 LCA+最小生成树

来源:程序员人生   发布时间:2016-07-04 11:46:44 阅读次数:577次

点击打开链接

题意:给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; }

生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生