题解 P4180 【【模板】严格次小生成树[BJWC2010]】
题目大意：
给定一个无向图，求出该图的次小生成树。
点数n≤100 000 边数m≤300 000
做法其实是比较简单的，首先我们求出给定图中的最小生成树，然后我们枚举每一条非树边，将其加入生成树中，可以证明这样一定会出现一个环，我们只需要在这个环中找到除去这条边以外最大的边,(又因为是严格次小生成树，所以还有找次小的，以防最大值与非树边边权相等），将它删去，然后得到另一个生成树，记录一下ans，对于所有非树边枚举得到的ans只要取一个最小值就可以了（因为是次小生成树）
但是这种做法的复杂度有点大，我们来分析一下：求最小生成树是O(n)，（由于并查集时间复杂度可以看作是一个常数），枚举非选择的边是O(m)，每一次求最大值（和次大值）也是O(m)，所以渐近时间复杂度是O(m^2)，如果要通过这道题还是差了很多。
那么我们进行优化：
很显然最小生成树不能优化，每一条非树边都必须被枚举，所以我们只能在求最大值上下手了。
考虑到我们在加入该非树边之前应该是一颗没有环的树，那么求一段路径上的最大值我们是会做的，树链剖分？代码量过于大了，那么我们考虑另一种做法：树上倍增LCA
其实LCA可以干很多事情的。。。
关于LCA求树上两点路径中边权最大值，这个其实是比较简单的，我们在原来的基础上开一个w[u][i]，表示从u向上跳2^i个点，这一段路径的最大值
动态转移方程也是比较显然的：我们假定f[u][i]表示从u向上跳2^i个点到达点的坐标，那么就有w[u][i+1]=max(w[u][i],w[f[u][i]][i])
所以我们只需要就从这两个点分别跳到他们的LCA处，每一次取最大值就可以了，这样我们就将m^2的算法转化成了mlogn,这样通过这道题就轻松加愉快了
但是我们忽略了一点：
题目中要求严格次小，但是这种做法很有可能就是和最小生成树相等，那么我们还需要解决这个难题。
其实也不算是难题，只是在原来的基础上多记录一个次大值，我们假设w2[u][i]表示从u向上跳2^i个单位，这段路径上的次大值。
动态转移方程就是：当w[u][i]>w[f[u][i]][i] w2[u][i+1]=max(w[f[u][i]][i],w2[f[u][i]][i])
当w[u][i]<w[f[u][i]][i] w2[u][i+1]=max(w[u][i],w2[f[u][i]][i])
当相等时，就继承上一个段的就可以了
那么我们就圆满的解决了这道题，总复杂度：mlogn+n*k k为一个比较小的常数
还有一些注意事项：
1.inf要足够大 因为这个边权之和很大很大
2.建树时要建反向边，谁知道给定的两个点相对顺序呢？
最后，附上本题代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
//Debug Yufenglin
#define dej printf("Running\n");
#define dep1(x) cout<<#x<<"="<<x<<endl;
#define dep2(x,y) cout<<#x<<"="<<x<<' '<<#y<<"="<<y<<endl;
#define dep3(x,y,z) cout<<#x<<"="<<x<<' '<<#y<<"="<<y<<' '<<#z<<"="<<z<<endl;
//Standfor Yufenglin
#define LL long long
#define LB long double
#define reg register
#define il inline
#define inf 1e8
#define maxn 100000
#define maxm 300000
struct EDGE
{
LL u,v,w;
};
struct TREE
{
LL to,val,nxt;
};
TREE tree[maxm+5];
EDGE edge[maxm+5];
LL n,m;
LL fa[maxn+5],f[maxn+5][30],w1[maxn+5][30],maxw1,maxw2,cnt,num;
LL head[maxn+5],dep[maxn+5],w2[maxn+5][30],ans,minans=1e16,sum;
bool vis[maxm+5];
bool cmp(EDGE x,EDGE y)
{
return x.w<y.w;
}
void add(LL x,LL y,LL z)
{
edge[++cnt].u=x;
edge[cnt].v=y;
edge[cnt].w=z;
}
void addedge(LL x,LL y,LL z)
{
tree[++num].to=y;
tree[num].val=z;
tree[num].nxt=head[x];
head[x]=num;
}
LL find(LL x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void dfs(LL u,LL fa)
{
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=0; i<=25; i++)
{
f[u][i+1]=f[f[u][i]][i];
w1[u][i+1]=max(w1[u][i],w1[f[u][i]][i]);
w2[u][i+1]=max(w2[u][i],w2[f[u][i]][i]);
if(w1[u][i]>w1[f[u][i]][i]) w2[u][i+1]=max(w2[u][i+1],w1[f[u][i]][i]);
if(w1[u][i]<w1[f[u][i]][i]) w2[u][i+1]=max(w2[u][i+1],w1[u][i]);
}
for(int i=head[u]; i; i=tree[i].nxt)
{
if(tree[i].to==fa) continue;
w1[tree[i].to][0]=tree[i].val;
dfs(tree[i].to,u);
}
}
LL LCA(LL x,LL y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=25; i>=0; i--)
{
if(dep[f[x][i]]>=dep[y])
{
x=f[x][i];
}
if(x==y) return x;
}
for(int i=25; i>=0; i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
LL query(LL x,LL y,LL d)
{
LL anst=-1;
for(int i=25;i>=0;i--)
{
if(dep[f[x][i]]>=dep[y])
{
if(d!=w1[x][i]) anst=max(anst,w1[x][i]);
else anst=max(anst,w2[x][i]);
x=f[x][i];
}
}
return anst;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(int i=1; i<=m; i++)
{
LL x,y,z;
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z);
}
sort(edge+1,edge+cnt+1,cmp);
for(int i=1; i<=n; i++) fa[i]=i;
for(int i=1; i<=m; i++)
{
if(find(edge[i].u)!=find(edge[i].v))
{
addedge(edge[i].u,edge[i].v,edge[i].w);
addedge(edge[i].v,edge[i].u,edge[i].w);
fa[find(edge[i].u)]=find(edge[i].v);
ans+=edge[i].w;
vis[i]=1;
sum++;
}
if(sum==n-1) break;
}
for(int i=1;i<=n;i++) w2[i][0]=-1;
dfs(1,0);
for(int i=1; i<=m; i++)
{
if(vis[i]==0)
{
LL lca=LCA(edge[i].u,edge[i].v);
LL maxu=query(edge[i].u,lca,edge[i].w);
LL maxv=query(edge[i].v,lca,edge[i].w);
minans=min(minans,ans-max(maxu,maxv)+edge[i].w);
}
}
printf("%lld\n",minans);
return 0;
}