首页 > 代码库 > uva 11354 bond 最小生成树
uva 11354 bond 最小生成树
n个城市通过m条无向边连接,回答q个询问,每个询问形式为s,t,要找到一条s到t的路使得这条路上的最大危险系数最小。
还是最小瓶颈路,可是要快速回答每次询问,先求出最小生成树,转化为有根树,即找到s到t的路径上的最大边,在这一过程中倍增查找。
预处理的复杂度为nlogn,每次查询为logn。
#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define maxn 100000 + 10struct Edge{ int u,v,w;}e[100100];int cmp(Edge a,Edge b){ return a.w<b.w;}int n,m;vector <int> G[maxn],C[maxn];int pa[maxn],fa[maxn],cost[maxn],L[maxn];int anc[maxn][20],maxcost[maxn][20];int find(int x){ if(pa[x]==x) return x; else return pa[x]=find(pa[x]);}void dfs(int u,int father,int level){ int i; L[u]=level; for(i=0;i<G[u].size();i++) { int v=G[u][i]; if(v!=father) { fa[v]=u; cost[v]=C[u][i]; dfs(v,u,level+1); } }}void pre(){ int i,j; for(i=0;i<n;i++) { anc[i][0]=fa[i];maxcost[i][0]=cost[i]; for(j=1;(1<<j)<n;j++) anc[i][j]=-1; } for(j=1;(1<<j)<n;j++) for(i=0;i<n;i++) { if(anc[i][j-1]!=-1) { int a=anc[i][j-1]; anc[i][j]=anc[a][j-1]; maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]); } }}int query(int p,int q){ int tmp,log,i; if(L[p]<L[q]) swap(p, q); for(log=1;(1<<log)<=L[p];log++);log--; int ans=-1000000000; for(i=log;i>=0;i--) if(L[p]-(1<<i)>=L[q]) { ans=max(ans,maxcost[p][i]); p=anc[p][i]; } if(p==q) return ans; for(i=log;i>=0;i--) { if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]) { ans=max(ans,maxcost[p][i]);p=anc[p][i]; ans=max(ans,maxcost[q][i]);q=anc[q][i]; } } ans=max(ans,cost[p]); ans=max(ans,cost[q]); return ans;}int main(){ int kcas=0; while(scanf("%d%d",&n,&m)!=EOF) { int i,j; int x,y,d; for(i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&d); e[i].u=x-1; e[i].v=y-1; e[i].w=d; } sort(e,e+m,cmp); for(i=0;i<n;i++) {pa[i]=i;G[i].clear();C[i].clear();} for(i=0;i<m;i++) { x=e[i].u; y=e[i].v; d=e[i].w; int fx=find(x); int fy=find(y); if(fx!=fy) { pa[fx]=fy; G[x].push_back(y);C[x].push_back(d); G[y].push_back(x);C[y].push_back(d); } } dfs(0,-1,0); pre(); int que; if(++kcas!=1) printf("\n"); scanf("%d",&que); while(que--) { scanf("%d%d",&x,&y); printf("%d\n",query(x-1,y-1)); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。