BZOJ 3732: Network（Kruskal+LCA倍增）
Posted On 2017年11月2日
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 < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
Solution
Kruskal+LCA倍增
证明（伪）：对于每两个点u,v，如果存在在u,v路径上且比最小生成树小的边，在Kruskal枚举边数时其必定被考虑并加入，即对于所有点对的路径，Kruskal都尽量取最短了
注意：不能使用LCA Tarjan （无法logn查询最大值)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; inline int read() { register int f=1,k=0;register char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=30000*2+10; struct mc{ int x,y,val; }edge[maxn]; struct mczhuang{ int too,val,nxt; }tree[maxn]; int f[maxn],last[maxn],logn,dep[maxn],fa[maxn][22],mx[maxn][22]; bool vis[maxn],used[maxn]; inline bool cmp(const mc&a,const mc&b){return a.val<b.val;} inline int max(const int&a,const int&b){return a>b?a:b;} int find(const int&x){return f[x]==x?x:f[x]=find(f[x]);} void dfs(int now,int father,int depth,int val) { dep[now]=depth;fa[now][0]=father;mx[now][0]=val; for (register int i=1;i<=logn;i++)fa[now][i]=fa[fa[now][i-1]][i-1], mx[now][i]=max(mx[now][i-1],mx[fa[now][i-1]][i-1]); for (register int i=last[now];i;i=tree[i].nxt)if (tree[i].too!=father)dfs(tree[i].too,now,depth+1,tree[i].val); } inline int query(int u,int v) { register int ans=0; if (dep[u]>dep[v])swap(u,v); for (register int i=logn;i>=0;i--) if (dep[u]<=dep[fa[v][i]])ans=max(ans,mx[v][i]),v=fa[v][i]; if (u==v)return ans; for (register int i=logn;i>=0;i--) if (fa[u][i]!=fa[v][i])ans=max(ans,max(mx[v][i],mx[u][i])),u=fa[u][i],v=fa[v][i]; ans=max(ans,max(mx[u][0],mx[v][0])); return ans; } int main() { register int n=read(),m=read(),k=read(),a,b,c,tot=0;while (n>(1<<logn))logn++; for (register int i=1;i<=n;i++)f[i]=i; for (register int i=1;i<=m;i++) a=read(),b=read(),c=read(),edge[i].x=a,edge[i].y=b,edge[i].val=c; sort(edge+1,edge+1+m,cmp); for (register int i=1;i<=m;i++) { a=find(edge[i].x);b=find(edge[i].y); if (a!=b)tree[++tot].nxt=last[edge[i].x],last[edge[i].x]=tot,tree[tot].too=edge[i].y, tree[++tot].nxt=last[edge[i].y],last[edge[i].y]=tot,tree[tot].too=edge[i].x, tree[tot].val=tree[tot-1].val=edge[i].val,f[a]=b; } dfs(1,0,1,0); while(k--) { a=read();b=read(); printf("%d\n",query(a,b)); } } |
博主太强了%%%
而且我也叫Michael 博客主题还是一样的（
%%%握爪