首页 > 代码库 > luogu 1967 货车运输(最大瓶颈生成树+LCA)
luogu 1967 货车运输(最大瓶颈生成树+LCA)
题意:给出一颗n个点的图,q个询问,每次询问u到v的路径中最小的边最大是多少。
图的最大瓶颈生成树有一个性质,对于该图的任意两个点,在树中他们之间路径的最小边最大。
由于这个图不一定联通,于是我们对它的联通块都求一次最大瓶颈生成树。
每次询问就变成了在最大瓶颈生成树上找出u到v路径的最小边。
这个显然可以用LCA维护点到它的2^x祖先之间的边的最小值来解决。
# include <cstdio> # include <cstring> # include <cstdlib> # include <iostream> # include <vector> # include <queue> # include <stack> # include <map> # include <set> # include <cmath> # include <algorithm> using namespace std; # define lowbit(x) ((x)&(-x)) # define pi acos(-1.0) # define eps 1e-7 # define MOD 1024523 # define INF 1000000000 # define mem(a,b) memset(a,b,sizeof(a)) # define FOR(i,a,n) for(int i=a; i<=n; ++i) # define FO(i,a,n) for(int i=a; i<n; ++i) # define bug puts("H"); # define lch p<<1,l,mid # define rch p<<1|1,mid+1,r # define mp make_pair # define pb push_back typedef pair<int,int> PII; typedef vector<int> VI; # pragma comment(linker, "/STACK:1024000000,1024000000") typedef long long LL; int Scan() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } void Out(int a) { if(a<0) {putchar(‘-‘); a=-a;} if(a>=10) Out(a/10); putchar(a%10+‘0‘); } const int N=10005; //Code begin... const int DEG=20; struct Edge{int p, next, w;}edge[N<<1]; struct Node{int u, v, w;}node[N*10]; int head[N], cnt=1, F[N], from[N]; int fa[N][DEG], mi[N][DEG], deg[N]; queue<int>que; void add_edge(int u, int v, int w){edge[cnt].p=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;} bool comp(Node a, Node b){return a.w>b.w;} int find(int x){return F[x]==-1?x:F[x]=find(F[x]);} void Kruscal(int n){ mem(F,-1); sort(node+1,node+2*n+1,comp); FOR(i,1,2*n) { int u=node[i].u, v=node[i].v, t1=find(u), t2=find(v); if (t1!=t2) add_edge(u,v,node[i].w), add_edge(v,u,node[i].w), F[t1]=t2; } } void BFS(int root){ deg[root]=0; fa[root][0]=root; mi[root][0]=INF; que.push(root); while (!que.empty()) { int tmp=que.front(); que.pop(); FO(i,1,DEG) fa[tmp][i]=fa[fa[tmp][i-1]][i-1], mi[tmp][i]=min(mi[tmp][i-1],mi[fa[tmp][i-1]][i-1]); for (int i=head[tmp]; i; i=edge[i].next) { int v=edge[i].p; if (v==fa[tmp][0]) continue; deg[v]=deg[tmp]+1; fa[v][0]=tmp; mi[v][0]=edge[i].w; que.push(v); } } } int LCA(int u, int v){ int ans=INF; if (deg[u]>deg[v]) swap(u,v); int hu=deg[u], hv=deg[v], tu=u, tv=v; for (int det=hv-hu, i=0; det; det>>=1, ++i) if (det&1) ans=min(ans,mi[tv][i]), tv=fa[tv][i]; if (tu==tv) return ans; for (int i=DEG-1; i>=0; --i) { if (fa[tu][i]==fa[tv][i]) continue; ans=min(ans,mi[tu][i]); ans=min(ans,mi[tv][i]); tu=fa[tu][i]; tv=fa[tv][i]; } return min(ans,min(mi[tu][0],mi[tv][0])); } int main () { int n, m, q, u, v; scanf("%d%d",&n,&m); FOR(i,1,m) scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w); Kruscal(m); int pos=0; FOR(i,1,n) { int v=find(i); if (from[v]==0) from[v]=1, BFS(v); } scanf("%d",&q); while (q--) { scanf("%d%d",&u,&v); if (find(u)!=find(v)) {puts("-1"); continue;} printf("%d\n",LCA(u,v)); } return 0; }
luogu 1967 货车运输(最大瓶颈生成树+LCA)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。