[BJWC2010] 严格次小生成树
题意：
给出无向图的点数与边数，求严格次小生成树的边权和。详见：[BJWC2010] 严格次小生成树。
注意：是严格次小的树，即：必须是大于且仅大于最小生成树的边权和。
思路：
1、基于题目给出的数据范围，是属于稀疏无向图，最好用Kruskal算法，生成最小生成树，并保存MST的信息、边权和。试过用Prim算法耗时相对较高；
2、DFS分别维护路径上的最大值与次大值，我用的是倍增数组；
3、枚举所有未用的边，求出两点的LCA，可以用倍增或者Tarjan离线算法计算LCA。由于Kruskal算法是按边权排序，对于离线查询LCA是按点操作，需要将未用边作为查询的两个点，有个额外的双向存点的耗时开销，通过提交对比总耗时增加155ms，达到了726ms。好处是相对简单，DFS时直接求出，不需要额外倍增再求LCA。
4、求点到LCA的最大值边权，如果与查询的边权相同，则取其次大值。
5、取两点到LCA的最大值，用查询的这个边权减去该最大值，即为目标之一，直到遍历完所有未用边，取其差的最小值。最后用原MST的边权和加上该差值的最小值即为严格次小生成树。
附上两种方法的AC代码：
1、倍增算法：
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
bool vis[300005];
int n,m,f[maxn],dep[maxn],p[maxn][20],w1[maxn][20],w2[maxn][20];
vector<pair<int,int>> tree[maxn];
long long sum;
struct node{int u,v,dis;bool operator < (const node& E) const{return dis<E.dis;}
}e[300005];
inline int read() { //快读int f = 1, x = 0;char ch;do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');return f * x;
}
int myfind(int x){return x==f[x]?x:f[x]=myfind(f[x]);
}
void unionSet(int x,int y){ //按秩合并，优化树深if (dep[x] > dep[y]) {f[y]=x; }else if (dep[x] < dep[y]) {f[x] = y; }else {f[y] =x; dep[x]++; }
}
void Kruskal(){//生成MSTint cnt=0;for(int i=1;i<=n;i++) f[i]=i;sort(e+1,e+m+1);for(int i=1;i<=m;i++){if(e[i].u==e[i].v||(e[i].u==e[i-1].u&&e[i].v==e[i-1].v)) {vis[i]=1;continue;}//取消自环和重复边int fx=myfind(e[i].u),fy=myfind(e[i].v);if(fx!=fy){unionSet(fx,fy);sum+=e[i].dis,vis[i]=1,cnt++;tree[e[i].u].push_back({e[i].v,e[i].dis}),tree[e[i].v].push_back({e[i].u,e[i].dis});}if(cnt==n-1) break;}
}
void dfs(int u,int fa,int d){dep[u]=dep[fa]+1;p[u][0]=fa;w1[u][0]=d;w2[u][0]=INT_MIN;for(int i=1;(1<<i)<=dep[u];i++){ //预处理倍增数组
// for(int i=1;i<=19;i++){ 优化无用循环p[u][i]=p[p[u][i-1]][i-1];w1[u][i]=max(w1[u][i-1],w1[p[u][i-1]][i-1]);w2[u][i]=max(w2[u][i-1],w2[p[u][i-1]][i-1]);if(w1[u][i-1]>w1[p[u][i-1]][i-1]) w2[u][i]=max(w2[u][i],w1[p[u][i-1]][i-1]);else if(w1[u][i-1]<w1[p[u][i-1]][i-1]) w2[u][i]=max(w2[u][i],w1[u][i-1]);}for(auto &v:tree[u])if(v.first!=fa) dfs(v.first,u,v.second);
}
int LCA(int u,int v){//倍增求LCAif(dep[u]<dep[v]) swap(u,v);for(int i=log2(dep[u]-dep[v]);i>=0;--i)
// for(int i=19;i>=0;--i) 优化无用循环if(dep[p[u][i]]>=dep[v]) u=p[u][i];if(u==v) return u;for(int i=log2(dep[u]);i>=0;--i) //优化无用循环if(p[u][i]^p[v][i]) u=p[u][i],v=p[v][i]; //异或运算:^表示不相等return p[u][0];
}
int maxd(int u,int v,int d){//求到LCA最大值int maxs=INT_MIN;for (int i=log2(dep[u]);i>=0;--i){
// for (int i=19;i>=0;--i){ 优化无用循环if(dep[p[u][i]]>=dep[v]){if(d!=w1[u][i]) maxs=max(maxs,w1[u][i]);else maxs=max(maxs,w2[u][i]);u=p[u][i];} }return maxs;
}
int mind(){ //求最小的边权差int ans=INT_MAX;for(int i=1;i<=m;i++){if(!vis[i]){ //遍历没有用到的边int lca=LCA(e[i].u,e[i].v);int s=max(maxd(e[i].u,lca,e[i].dis),maxd(e[i].v,lca,e[i].dis));if(s>0) ans=min(ans,e[i].dis-s);}}return ans;
}
int main(){n=read(),m=read();for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].dis=read();Kruskal();memset(dep,0,sizeof(dep));dfs(myfind(1),0,0);printf("%lld",mind()+sum);return 0;
}2、Tarjan离线算法
#include <bits/stdc++.h>
using namespace std;
const int maxn=100001;
int n,m,u,v,d,ans=INT_MAX,cnt,f[maxn],dep[maxn],p[maxn][20],w1[maxn][20],w2[maxn][20];
vector<pair<int,int>> tree[maxn];
bool vis[maxn];
long long sum;
struct node{int x,y,dis;bool operator < (const node& E) const{return dis>E.dis;}
};
vector<node> query[maxn];
priority_queue<node> q;
inline int read() { //快读int f = 1, x = 0;char ch;do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');return f * x;
}
int myfind(int x){return x==f[x]?x:f[x]=myfind(f[x]);
}
void unionSet(int x,int y){ //按秩合并，较矮的树合并到较高的树if (dep[x] > dep[y]) {f[y]=x; }else if (dep[x] < dep[y]) {f[x] = y; }else {f[y] =x; dep[x]++; }
}
void Kruskal(){ //最小生成树for(int i=1;i<=n;i++) f[i]=i;while(!q.empty()){u=q.top().x,v=q.top().y,d=q.top().dis;if(cnt<n-1){int fx=myfind(u),fy=myfind(v);if(fx!=fy){unionSet(fx,fy);sum+=d,cnt++;tree[u].push_back({v,d}),tree[v].push_back({u,d});}else query[u].push_back({v,0,d}),query[v].push_back({u,0,d});}else query[u].push_back({v,0,d}),query[v].push_back({u,0,d});q.pop();}
}
int maxd(int u,int v,int d){//求到LCA最大值int maxs=INT_MIN;for (int i=log2(dep[u]);i>=0;--i){
// for (int i=19;i>=0;--i){ 优化无用循环if(dep[p[u][i]]>=dep[v]){if(d!=w1[u][i]) maxs=max(maxs,w1[u][i]);else maxs=max(maxs,w2[u][i]);u=p[u][i];} }return maxs;
}
void dfs(int u,int fa,int d){ //tarjan离线查询求LCAdep[u]=dep[fa]+1,vis[u]=1;p[u][0]=fa;w1[u][0]=d;w2[u][0]=INT_MIN;for(int i=1;(1<<i)<=dep[u];i++){ //预处理倍增数组
// for(int i=1;i<=19;i++){ 优化无用循环p[u][i]=p[p[u][i-1]][i-1];w1[u][i]=max(w1[u][i-1],w1[p[u][i-1]][i-1]);w2[u][i]=max(w2[u][i-1],w2[p[u][i-1]][i-1]);if(w1[u][i-1]>w1[p[u][i-1]][i-1]) w2[u][i]=max(w2[u][i],w1[p[u][i-1]][i-1]);else if(w1[u][i-1]<w1[p[u][i-1]][i-1]) w2[u][i]=max(w2[u][i],w1[u][i-1]);}for(auto &v:tree[u])if(v.first!=fa) dfs(v.first,u,v.second),f[v.first]=u;for (auto &q:query[u]) { //处理与u有关的查询,求LCAif (vis[q.x]&&!q.y){ //后面的条件避免重复求LCAint lca = myfind(q.x);int s=max(maxd(q.x,lca,q.dis),maxd(u,lca,q.dis));if(s>0) ans=min(ans,q.dis-s);q.y=1;}}
}
int main(){n=read(),m=read();;while(m--){u=read(),v=read(),d=read();if(u!=v)q.push({u,v,d});}Kruskal();memset(dep,0,sizeof(dep));u=myfind(1);for(int i=1;i<=n;i++) f[i]=i;dfs(u,0,0);printf("%lld",sum+ans);return 0;
}附耗时截图：
