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 ;
}

最新文章

  1. ASP.NET Core MVC 在linux上的创建及发布
  2. 修改注册表来修改IE的设置---资料汇总
  3. javascript设计模式-迭代器模式(Iterator)
  4. 17.2 The DispatcherServlet
  5. 哆啦A梦连连看游戏源码完整版
  6. 逆序对的相关问题:bzoj1831,bzoj2431
  7. perl命令批量替换文件内容
  8. 关于arm处理器 内存编址模式 与 字节对齐方式 (转)
  9. css盒子模型、文档流、相对与绝对定位、浮动与清除模型
  10. NFC简介
  11. 修改mysql的默认字符集
  12. 1-5html文件基本结构
  13. SqlBulkCopy 参数配置示例
  14. hdu1568 Fibonacci---前4位
  15. css基础系列
  16. Mysql初学入门
  17. [Linux]流媒体服务器概述
  18. mysql定时备份
  19. HDU 6170 dp
  20. android 8.0变更

热门文章

  1. 用机智云做PWM占空比控制电机,物联网智能家居应用
  2. maven的编译规范
  3. StarUML 3.0 破解方法
  4. IT技术管理者的自我修养
  5. 已知词频生成词云图(数据库到生成词云)--generate_from_frequencies(WordCloud)
  6. 【Java例题】2.2 分数类
  7. C++基础之:扫雷破解
  8. Liunx查看后1000行的命令以及查看中间部分
  9. 《深入理解Java虚拟机》-(实战)练习修改class文件
  10. Mysql超详解