[BJWC2010] 严格次小生成树
2024-10-21 05:46:09
传送门：>Here<
给出一张带权无向图，求其严格次小生成树。（$n \leq 10^5$）
解题思路
图的生成树有一个性质：将一条非树边加入后必定形成环。Kruscal求最小生成树其实就是一个贪心地过程：剔除每个环上最大的那一条边。
那么反过来，求次小生成树就是在某个环上换回最大边，删去原来最大边以保证增量最小的过程。由于题目要求严格，会碰到最大边等于原先最大边的情况，此时就删去原先严格次大边。
于是现在就是一个数据结构维护的问题了。预处理出最小生成树，维护树链上最大值和次大值，可以树剖或者在倍增LCA的过程中维护。
如果够无聊，LCT也可以。LCT求最小生成树不用预先对边排序，由于可以动态连边断边，是完全可以根据最小生成树的性质直接维护的——每发现一条边形成了环，如果更优就直接LinkCut更新，保证了全局的最优性。再在Splay上维护边权的最小值就解决了。
$Code$
/*By QiXingzhi*/
#include <cstdio>
#include <vector>
#include <algorithm>
#define N (100010)
#define M (300010)
#define INF (21474836470000)
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
typedef long long ll;
using namespace std;
#define int ll
inline void read(int &x){
x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar(); x *= w;
}
struct Edge{
int x,y,z;
};
struct Graph{
int to,cost;
};
Edge a[M];
bool t_edge[M];
vector <Graph> G[N];
vector <Graph> Gt[N];
int n,m,krus,krus_num,x,y,ans;
int par[N],f[N][],gmax[N][],gsec[N][],fa[N],wei[N],depth[N];
inline void AddEdge(int u, int v, int w){
Graph e;
e.to = v;
e.cost = w;
G[u].push_back(e);
}
inline void AddEdge_2(int u, int v, int w){
Graph e;
e.to = v;
e.cost = w;
Gt[u].push_back(e);
}
inline void Swap(int& a, int &b){
int t = a;
a = b;
b = t;
}
inline bool kruscal_sort_comp(const Edge& a, const Edge& b){
return a.z < b.z;
}
int krus_find(int x){
if(par[x] == x) return x;
par[x] = krus_find(par[x]);
return par[x];
}
void build_tree(int x, int ff){
int sz = Gt[x].size();
int to;
for(int i = ; i < sz; ++i){
to = Gt[x][i].to;
if(to != ff){
fa[to] = x;
wei[to] = Gt[x][i].cost;
build_tree(to, x);
}
}
}
void lca_dfs(int x, int d){
depth[x] = d;
for(int k = ; (<<k) < d; ++k){
f[x][k] = f[f[x][k-]][k-];
gmax[x][k] = Max(gmax[x][k-], gmax[f[x][k-]][k-]);
if(gmax[x][k-] == gmax[f[x][k-]][k-]){
gsec[x][k] = Max(gsec[x][k-], gsec[f[x][k-]][k-]);
}
else if(gmax[x][k-] > gmax[f[x][k-]][k-]){
gsec[x][k] = Max(gsec[x][k-], gmax[f[x][k-]][k-]);
}
else if(gmax[x][k-] < gmax[f[x][k-]][k-]){
gsec[x][k] = Max(gmax[x][k-], gsec[f[x][k-]][k-]);
}
}
int sz = Gt[x].size();
int to;
for(int i = ; i < sz; ++i){
to = Gt[x][i].to;
if(to != f[x][]){
lca_dfs(to, d+);
}
}
}
inline void Update(int i){
int u = a[i].x, v = a[i].y, w = a[i].z, res;
int val1 = -INF, val2 = -INF;
if(depth[u] > depth[v]) Swap(u,v);
for(int k = ; k >= ; --k){
if(depth[u] <= depth[v] - (<<k)){
if(gmax[v][k] < val1){
val2 = Max(gmax[v][k], val2);
}
else if(gmax[v][k] == val1){
val2 = Max(val2, gsec[v][k]);
}
else if(gmax[v][k] > val1){
val2 = Max(gsec[v][k], val1);
}
val1 = Max(val1, gmax[v][k]);
v = f[v][k];
}
}
if(u != v){
for(int k = ; k >= ; --k){
if(f[u][k] != f[v][k]){
if(gmax[u][k] < val1){
val2 = Max(val2, gmax[u][k]);
}
else if(gmax[u][k] == val1){
val2 = Max(val2, gsec[u][k]);
}
else{
val2 = Max(val1, gsec[u][k]);
}
if(gmax[v][k] < val1){
val2 = Max(val2, gmax[v][k]);
}
else if(gmax[v][k] == val1){
val2 = Max(val2, gsec[v][k]);
}
else{
val2 = Max(val1, gsec[v][k]);
}
val1 = Max(val1, gmax[u][k]);
val1 = Max(val1, gmax[v][k]);
u = f[u][k];
v = f[v][k];
}
}
val1 = Max(val1, Max(gmax[u][], gmax[v][]));
if(val2 < gmax[u][] && gmax[u][] < val1) val2 = gmax[u][];
if(val2 < gmax[v][] && gmax[v][] < val1) val2 = gmax[v][];
}
if(val1 < w){
res = krus - val1 + w;
}
else if(val1 == w){
res = krus - val2 + w;
}
ans = Min(ans, res);
}
#undef int
int main(){
#define int ll
// freopen(".in","r",stdin);
read(n), read(m);
for(int i = ; i <= m; ++i){
read(a[i].x), read(a[i].y), read(a[i].z);
AddEdge(a[i].x,a[i].y,a[i].z);
AddEdge(a[i].y,a[i].x,a[i].z);
}
sort(a+, a+m+, kruscal_sort_comp);
for(int i = ; i <= n; ++i) par[i] = i;
for(int i = ; i <= m; ++i){
x = krus_find(a[i].x);
y = krus_find(a[i].y);
if(x != y){
par[x] = y;
++krus_num;
krus += a[i].z;
t_edge[i] = ;
AddEdge_2(a[i].x,a[i].y,a[i].z);
AddEdge_2(a[i].y,a[i].x,a[i].z);
}
if(krus_num >= n-) break;
}
build_tree(, );
for(int i = ; i <= n; ++i){
f[i][] = fa[i];
gmax[i][] = wei[i];
gsec[i][] = -INF;
}
lca_dfs(,);
ans = INF;
for(int i = ; i <= m; ++i){
if(!t_edge[i]){
Update(i);
}
}
printf("%lld",ans);
return ;
}
最新文章
- Objective-C之run loop详解［转］
- linux 驱动学习笔记04--简单驱动
- jQuery Filterizr 筛选过滤
- css中的浮动以及清除浮动
- android ArrayAdapter BaseAdapter SimpleAdapter使用讲解
- leetcode 70
- ASP.NET MVC程序传值方式:ViewData，ViewBag，TempData和Session
- iOS中事件的传递和响应者链条
- Vmare12(虚拟机)安装Mac OS X Yosemite 10.10
- ShareSDK.xml 配置
- java中的字符编码方式
- C语言删除字符串中重复的字符
- cordova获取相册照片插件的使用方法：cordova-plugin-image-picker
- RESTful levels、HATEOAS
- 使用VS Code调试Node
- arcgis api for flex 开发入门
- 输出列表为字符串，并在最后一个值前加上and 4.10.1
- 用linq和datatable巧妙应用于微软报表rdlc
- 事件冒泡的应用——jq on的实现
- Codeforces Round #479 (Div. 3)解题报告