Minimum spanning tree for each edge(倍增LCA)
2024-08-30 13:29:24
https://vjudge.net/contest/320992#problem/J
暑期训练的题。
题意:给你一个n个点,m条边的无向图。对于每一条边,求包括该边的最小生成树。
思路:首先想到求一次整图的mst后,对每条边(u,v),如果该边在整图的最小生成树上,答案就是mst,否则,加入的边(u,v)会使原来的最小生成树成环,可以通过lca确定该环,那么只要求出u到lca(u,v)路径上的最大边权和v到lca(u,v)路径上的最大边权中的最大值mx,mst-mx+w[u.v]就是答案。其中gx[u][i]表示节点u到其第2^i个祖先路径上的最大边权。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + ;
const int DEG = ;
typedef long long ll;
struct edge {
int v, w, next;
edge() {}
edge(int v, int w, int next) : v(v), w(w), next(next){}
}e[N << ]; int head[N], tot;
int fa[N][DEG], deg[N];
int gx[N][DEG];
void init() {
memset(head, -, sizeof head);
tot = ;
}
void addedge(int u, int v, int w) {
e[tot] = edge(v, w, head[u]);
head[u] = tot++;
}
void BFS(int root) {
queue<int> que;
deg[root] = ;
fa[root][] = root;
gx[root][] = ;
que.push(root);
while(!que.empty()) {
int tmp = que.front();
que.pop();
for(int i = ; i < DEG; ++i) {
fa[tmp][i] = fa[ fa[tmp][i - ] ][i - ];
gx[tmp][i] = max(gx[tmp][i - ], gx[ fa[tmp][i - ] ][i - ]);
// printf("[%d %d] ", tmp, gx[tmp][i]);
}
// puts("");
for(int i = head[tmp]; ~i; i = e[i].next) {
int v = e[i].v;
int w = e[i].w;
if(v == fa[tmp][]) continue;
deg[v] = deg[tmp] + ;
fa[v][] = tmp;
gx[v][] = w;
que.push(v);
}
}
}
int Mu, Mv;
ll LCA(int u, int v) {
Mu = Mv = -;
if(deg[u] > deg[v]) swap(u, v);
int hu = deg[u], hv = deg[v];
int tu = u, tv = v;
for(int det = hv - hu, i = ; det; det >>= , ++i)
if(det & ) { Mv = max(Mv, gx[tv][i]); tv = fa[tv][i]; }
if(tu == tv) return Mv;
for(int i = DEG - ; i >= ; --i) {
if(fa[tu][i] == fa[tv][i]) continue;
Mu = max(Mu, gx[tu][i]);
Mv = max(Mv, gx[tv][i]);
tu = fa[tu][i];
tv = fa[tv][i]; }
return max(max(Mu, gx[tu][]), max(Mv, gx[tv][]));
} int U[N], V[N], w[N], r[N], f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool cmp(int a, int b) { return w[a] < w[b]; }
ll MST;
int n, m;
void mst() { scanf("%d%d", &n, &m);
for(int i = ; i <= m; ++i) {
scanf("%d%d%d", &U[i], &V[i], &w[i]);
r[i] = i;
f[i] = i;
}
sort(r + , r + m + , cmp);
MST = ;
for(int i = ; i <= m; ++i)
{
int id = r[i];
int fu = find(U[id]);
int fv = find(V[id]);
if(fu != fv) {
MST += w[id];
f[ fu ] = fv;
addedge(U[id], V[id], w[id]);
addedge(V[id], U[id], w[id]);
}
}
}
int main() {
init();
mst();
BFS(); for(int i = ; i <= m; ++i) {
printf("%I64d\n", MST - LCA(U[i], V[i]) + w[i]);
}
return ;
}
最新文章
- ASP.NET Core MVC 在linux上的创建及发布
- 修改注册表来修改IE的设置---资料汇总
- javascript设计模式-迭代器模式(Iterator)
- 17.2 The DispatcherServlet
- 哆啦A梦连连看游戏源码完整版
- 逆序对的相关问题:bzoj1831,bzoj2431
- perl命令批量替换文件内容
- 关于arm处理器 内存编址模式 与 字节对齐方式 (转)
- css盒子模型、文档流、相对与绝对定位、浮动与清除模型
- NFC简介
- 修改mysql的默认字符集
- 1-5html文件基本结构
- SqlBulkCopy 参数配置示例
- hdu1568 Fibonacci---前4位
- css基础系列
- Mysql初学入门
- [Linux]流媒体服务器概述
- mysql定时备份
- HDU 6170 dp
- android 8.0变更