算法提高课汇总

次小生成树

一个带权图$G$, 将$G$的所有生成树按权值和从小到大排序, 其中第二小的称为次小生成树.

次小生成树分为两类:

• 非严格次小: $W(T’)\ge W(T)$. 其中用$T$和$T’$分别表示最小和次小生成树.

• 严格次小: $W(T’)\gt W(T)$.

求解方法

两种求解思路, 用非树边替换树边得到一颗新的生成树.

方法$1$

先求出最小生成树$T$, 删除任意一条边$e\in T$, 删除后再求一次不带$e$的最小生成树$T’$.
枚举$\forall e\in T$, 得到所有不带$e$生成树的$W(T’)$的最小值.

• 正确性证明: 从集合的角度考虑, 次小生成树$T’$一定至少存在一条边$e’\notin T$.
  可以以$T’$中不存在$T$中的某条边$e$作为集合划分,
  则方法$1$的过程就是将所有可能的子集都枚举一遍,
  得到所有子集的最小值.

• 时间复杂度: 我们用$Kruskal$算法求最小生成树,
  算法需要在删除任意一条边后求一次最小生成树.
  所以时间复杂度为$O(m\lg(m) + nm)$. 其中$m\lg(m)$
  是对所有边排序的时间, $nm$是求生成树的时间.

• 算法容易求解非严格次小生成树, 而计算严格次小生成树比较困难.

方法$2$

先求出最小生成树$T$, 依次枚举非树边$e\notin T$加入$T$构成环$C$, 删去$C$中一条边,
得到一颗新的生成树$T’$. 可以证明用这种方法一定可以得到次小生成树.

• 正确性证明: 算法过程相当于我们用一条非树边替换了一条树边.
  为证明算法正确可以证明:一定存在一个次小生成树$T’$,
  $T’$与$T$只有一条边不同.

• 首先证明算法对非严格次小生成树的正确性. 假设存在一颗次小生成树$T’$,
  $T’$与$T$不同的边数大于$1$条. 对最小生成树$T$的边按边权从小到达排序,
  找到第一个$T$与$T’$不同的边, 假设$T$选择的是$e$, 而$T’$选择的是$e’$.
  将$e$加入$T’$构成回路, 删除$e’$, 因为$e\le e’$, 所以经过此次操作
  后形成的次小生成树$T’\’, W(T’\’)\le W(T’)$. 经过此次操作后新的
  次小生成树边权不增, 且与最小生成树不同边数$-1$. 重复次操作直到边数只相差$1$为止.

• 证明算法对严格次小生成树的正确性. 假设存在一颗严格次小生成树$T’$,
  $T’$与$T$不同的边数大于$1$条. 实际上对于严格次小生成树,
  对于某条边$e’$不同于$T$中的$e$, 有$e’\ge e$, 并且有且仅有一条边
  满足$e’\gt e$, 否则不满足次小的限制. 我们可以保留这条$e’\gt e$,
  对其他$e’=e$的边的边按照上述方式替换即可.

• 时间复杂度: 在加入非树边$e’ = w(u, v)$时, 假设去掉原$u\rightarrow v$
  路径上的边$e$, 则新的生成树的权值和为$W(T) + w(e’) - w(e)$,
  为新生成树权重最小, 需要去路径上最大边权. 所以我们需要预处理从
  某点出发到达另一顶点路径上边权最大值, 可以用$dfs$解决, 时间复杂度$n^2$; 最小生成树可以用$Kruskal$求解. 所以题目时间复杂度为$O(m\lg(m) + n^2)$.

本题的思路有点类似AcWing 346. 走廊泼水节, 不同的是此时加的边是原图已经存在的边.

代码实现

• 注意: 因为可能会遇到所有非树边$e’$和上述$u\rightarrow v$最大路径值恰好全部相等的情况, 此时如果只计算
  路径最大值(最小的次小生成树)不能得到严格最小, 所以我们还要在$dfs$中计算$u\rightarrow u$中的
  第二大边权.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 510, M = 1e4 + 10;

int n, m;
int dist1[N][N], dist2[N][N]; //dist[v][u]: 从u出发, 到达v的路径过程中的边权最大值以及次大值
int p[N];
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx; //存储最小生成树 以方便dfs
struct Edge
{
    int u, v, w;
    bool flag; //是否在最小生成树中
    bool operator< (const Edge e) const
    {
        return w < e.w;
    }
}edge[M];

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}

void init(int n)
{
    for( int i = 1; i <= n; i ++ )
        p[i] = i;
}

int find(int x)
{
    return x == p[x] ? x : p[x] = find(p[x]);
}

ll kruskal()
{
    init(n);
    sort(edge, edge + m);
    memset(h, -1, sizeof h);

    ll sum = 0;
    for( int i = 0; i < m; i ++ )
    {
        int u = edge[i].u, v = edge[i].v, c = edge[i].w;
        int pu = find(u), pv = find(v);
        if( pu != pv )
        {
            sum += c;
            p[pu] = pv;
            edge[i].flag = true;
            add(u, v, c), add(v, u, c); 
        }
    }
    return sum;
}

//u:当前节点; last:上一个节点 防止两个点来回遍历; maxd:经过边权最大; smaxd:次大 
void dfs(int u, int last, int maxd, int smaxd, int d1[], int d2[])
{
    d1[u] = maxd; d2[u] = smaxd;
    for( int i = h[u]; ~i; i = ne[i] )
    {
        int v = e[i];
        if( v != last )
        {
            int td1 = maxd, td2 = smaxd; //暂存 因为不能影响到u到其他点的边权
            if( td1 < w[i] )
            {//更新最大以及次大
                td2 = td1; td1 = w[i];
            }
            else if( td2 < w[i] && w[i] < td1 )
            {//更新次大
                td2 = w[i];
            }
            dfs(v, u, td1, td2, d1, d2);//经过新的边权 更新maxd
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for( int i = 0; i < m; i ++ )
    {
        int u, v, c;
        cin >> u >> v >> c;
        edge[i] = {u, v, c};
    }

    ll sum = kruskal();

    for( int i = 1; i <= n; i ++ )  dfs(i, -1, 0, 0, dist1[i], dist2[i]);

    ll res = 1e18;
    for( int i = 0; i < m; i ++ )
    {
        if( !edge[i].flag )
        {//非树边
            int u = edge[i].u, v = edge[i].v, c = edge[i].w;
            if( c > dist1[u][v] )
            {//保证严格次小
                res = min(res, sum + c - dist1[u][v] );
            }
            else if( c > dist2[u][v] )
            {
                res = min(res, sum + c - dist2[u][v] );
            }
        }
    }
    printf("%lld\n", res);

    return 0;
}