BZOJ3732: Network(Kruskal重构树)
2018-07-22 05:46:52来源:博客园 阅读 ()
题意
Link
给出一张$n$个点的无向图,每次询问两点之间边权最大值最小的路径
$n \leqslant 15000, m \leqslant 30000, k \leqslant 20000$
Sol
很显然答案一定在最小生成树上,但是此题还有一个更为玄学的做法—Kruskal重构树
它是在Kruskal算法上改进而来的。
算法流程:
- 对于此题来说,将边权从小到大排序
- 用并查集维护两点的联通性,若祖先不相同,那么新建一个节点,权值为边权。左右儿子分别为两个点
这样建出来的树,我们称之为Kruskal重构树
它有许多美妙的性质
- 是一颗二叉树
- 两点的LCA的点权为原图中最大值最小的路径上的最大值
- 任意点的权值大于左右儿子的权值,是一个大根堆
对于此题的样例来说,建出来的图大概长这样
#include<cstdio> #include<algorithm> using namespace std; const int MAXN = 1e5 + 10, INF = 1e9, B = 19; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int fa[MAXN], f[MAXN][21], ch[MAXN][2], cnt, val[MAXN], deep[MAXN]; int N, M, K; struct Edge { int u, v, w; bool operator < (const Edge &rhs) const { return w < rhs.w; } }E[MAXN]; int head[MAXN], num = 0; inline void AddEdge(int x, int y, int z) { E[++num] = (Edge){x, y, z}; } int find(int x) { if(fa[x] == x) return fa[x]; else return fa[x] = find(fa[x]); } void Kruskal() { sort(E + 1, E + num + 1); int tot = 0; for(int i = 1; i <= M; i++) { int x = E[i].u, y = E[i].v; int fx = find(x), fy = find(y); if(fx == fy) continue; ch[++cnt][0] = fx, ch[cnt][1] = fy; fa[fa[x]] = fa[fa[y]] = f[fa[x]][0] = f[fa[y]][0] = cnt; val[cnt] = E[i].w; } } void dfs(int x) { if(!ch[x][0] && !ch[x][1]) return ; deep[ch[x][0]] = deep[ch[x][1]] = deep[x] + 1; dfs(ch[x][0]); dfs(ch[x][1]); } int LCA(int x, int y) { if(deep[x] < deep[y]) swap(x, y); for(int i = B; i >= 0; i--) if(deep[f[x][i]] >= deep[y]) x = f[x][i]; if(x == y) return x; for(int i = B; i >= 0; i--) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i]; return f[x][0]; } main() { //freopen("a.in", "r", stdin); cnt = N = read(); M = read(); K = read(); for(int i = 1; i <= N << 1; i++) fa[i] = i; for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); AddEdge(x, y, z); } Kruskal(); deep[cnt] = 1; dfs(cnt); for(int i = 1; i <= B; i++) for(int j = 1; j <= 2 * N; j++) f[j][i] = f[f[j][i - 1]][i - 1]; while(K--) { int x = read(), y = read(); // printf("%d\", LCA(x, y)); printf("%d\n", val[LCA(x, y)]); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 图论-最小生成树<Kruskal> 2019-10-28
- 洛谷P3366【模板】最小生成树-克鲁斯卡尔Kruskal算法详解附 2019-05-16
- 最小生成树---Kruskal算法 2018-12-04
- poj-2236 wireless network(并查集) 2018-12-04
- 洛谷P4197 Peaks(Kruskal重构树 主席树) 2018-09-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash