「BZOJ 1977」次小生成树

发表于 | | 阅读次数:
字数统计: 911 字

Description

题目链接：BZOJ 1977

小 C 最近学了很多最小生成树的算法，$\text{Prim}$ 算法、$\text{Kurskal}$ 算法、消圈算法等等。正当小 C 洋洋得意之时，小 P 又来泼小 C 冷水了。小 P 说，让小 C 求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是 $E_M$，严格次小生成树选择的边集是 $E_S$，那么需要满足（$\text{value}(e)$ 表示边 $e$ 的权值）：$\sum_{e \in E_M}\text{value}(e)<\sum_{e \in E_S}\text{value}(e)$

这下小 C 蒙了，他找到了你，希望你帮他解决这个问题。

数据范围：$1\le n\le 10^5$，$1\le m,\le 3\times 10^5$，$0\le \text{value}(e)\le 10^9$

Solution

事实上可以证明：有至少一个次小生成树，和最小生成树之间只有 $1$ 条边的差异。

我们先把最小生成树求出来，然后尝试用每一条不在生成树上的边去替换。

考虑不在最小生成树上的边 $(u,v,w)$（其中 $w$ 是边权），在链 $u-v$ 上找到一条最大的严格小于 $w$ 的边。可以注意到，$u-v$ 上肯定没有严格大于 $w$ 的边（否则就不是最小生成树了 QAQ）。我们倍增维护链上的最大边权，每次倍增往上跳时查找严格小于的边权即可。

时间复杂度：$O((n+m)\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <cstdio>
#include <algorithm>

const int N=1e5+5,M=3e5+5,logN=17;
int n,m,tot,lnk[N],ter[N<<1],nxt[N<<1],val[N<<1],dep[N],fa[N],f[N][logN],g[N][logN];
bool flg[M];
struct Edge {
    int u,v,w;
    bool operator < (const Edge &b) const {
        return w<b.w;
    }
} e[M];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
long long kruskal() {
    std::sort(e+1,e+m+1);
    for(int i=1;i<=n;++i) fa[i]=i;
    long long ans=0;
    for(int cnt=0,i=1;cnt<n-1&&i<=m;++i) {
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(find(u)==find(v)) continue;
        fa[find(u)]=find(v),add(u,v,w),add(v,u,w),ans+=w,flg[i]=1;
    }
    return ans;
}
void dfs(int u,int p) {
    dep[u]=dep[p]+1;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==p) continue;
        f[v][0]=u,g[v][0]=val[i];
        dfs(v,u);
    }
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) std::swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=16;i>=0;--i) if(d&(1<<i)) x=f[x][i];
    if(x==y) return x;
    for(int i=16;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int query(int u,int p,int w) {
    int d=dep[u]-dep[p],ans=-1;
    for(int i=16;i>=0;--i) if(d&(1<<i)) {
        if(w>g[u][i]) ans=std::max(ans,g[u][i]);
        u=f[u][i];
    }
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    long long sum=kruskal();
    dfs(1,0);
    for(int j=1;(1<<j)<=n;++j) for(int i=1;i<=n;++i) {
        f[i][j]=f[f[i][j-1]][j-1],g[i][j]=std::max(g[i][j-1],g[f[i][j-1]][j-1]);
    }
    long long ans=1LL<<60;
    for(int i=1;i<=m;++i) if(!flg[i]) {
        int u=e[i].u,v=e[i].v,w=e[i].w,x=lca(u,v);
        int mx=std::max(query(u,x,w),query(v,x,w));
        if(mx>0) ans=std::min(ans,sum-mx+w);
    }
    printf("%lld\n",ans);
    return 0;
}
0%