题解 P4180 【【模板】严格次小生成树[BJWC2010]】

· · 题解

　　思路大体一致:先用kruskal求出MST,再用通过加边和删边的操作求解.对此就不多说了.本篇题解主要讨论删边操作.

  1. 若去掉严格这一要求,那么要删除的边即为MST上两点间的最大权值.对此,可以考虑用kruskal重构树,树上两点间的LCA即为所求.
  2. 要求严格的话,直接判断即可,若LCA的点权与当前枚举边的点权相同, 暴力地遍历一下两点间的非叶子节点即可

　　PS:当然,LCA的过程还是可以优化的,转成求RMQ,可以做到O(1)的查询,\pm RMQ的话,可以做到O(n)的预处理 (然而并不会)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

#define IL inline

using namespace std;
typedef long long ll;

IL int read()
{
    int sum = 0;
    bool k = 1;
    char c = getchar();
    for(;'0' > c || c > '9'; c = getchar())
    if(c == '-') k = 0;
    for(;'0' <= c && c <= '9'; c = getchar())
        sum = sum * 10 + (c - '0');
    return k ? sum : -sum;
}

int n, m;

struct Side
{
    int u, v, w;
    bool f;
    bool operator < (const Side &b) const
    {   
        return w < b.w;
    }
}side[300005];

int fa[200005][18];
int dep[200005];
int weight[200005];
int lg[200005]; // 打标,卡卡常

int pa[200005];//并查集
IL int find(int x) { return pa[x] = (pa[x] == x ? x : find(pa[x])); }
IL bool join(int x, int y, int z, int &T)
{
    int x1 = find(x), y1 = find(y);
    if(x1 == y1) return 0;
    ++T;
    fa[x1][0] = fa[y1][0] = T + n;
    weight[T + n] = z;

    pa[x1] = pa[y1] = T + n;

    return 1;
}

IL ll kru()
{
    sort(side + 1, side + m + 1);

    for(int i = 1; i <= n; ++i)
    {
        pa[i] = i; pa[i + n] = i + n;
    }

    ll sum = 0;
    int T = 0;
    for(int i = 1; i <= m && T < n; ++i)
    if(join(side[i].u, side[i].v, side[i].w, T))
    {
        side[i].f = 1;
        //printf("%d\n",side[i].w);
        sum += side[i].w;
        //printf("%d\n", sum);
    }
    return sum;
}

IL int get_dep(int u)
{
    if(dep[u] != -1) return dep[u];
    if(!fa[u][0]) return dep[u] = 0;
    return dep[u] = get_dep(fa[u][0]) + 1;
}

IL void lca()
{
    int n2 = (n << 1) - 1;
    memset(dep, -1, sizeof(dep));
    for(int i = 1; i <= n2; ++i)
    if(dep[i] == -1)
        get_dep(i);
    //太懒不想建树,直接记忆化求dep
    for(int i = 2; i <= n2; ++i)
        lg[i] = lg[i >> 1] + 1;
    for(int j = 1; j <= lg[n2]; ++j)
    for(int i = 1; i <= n2; ++i)
    if(fa[i][j - 1])
        fa[i][j] = fa[fa[i][j - 1]][j - 1];
}

IL void swap_(int &x, int &y) { int tmp = x; x = y; y = tmp; }

IL int query(int x, int y)
{
    if(dep[x] < dep[y]) swap_(x, y);
    for(int t = dep[x] - dep[y]; t; t -= t & (-t))
        x = fa[x][lg[t & (-t)]];
    //蜜汁跳高度, lg表 + lowbit优化
    if(x == y) return x;
    for(int i = lg[dep[x]]; i >= 0; --i)
    if(fa[x][i] != fa[y][i])
    {
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}

IL void solve(ll sum)
{
    ll det = -1, w;
    for(int i = 1, p, x, y; i <= m; ++i)
    if(!side[i].f)
    {
        x = side[i].u; y = side[i].v;
        p = query(x, y);
        w = side[i].w - weight[p];
        if(w)
        {
            if(det == -1 || w < det) det = w;
        }else
        if(!w)
        {
            for(x = fa[x][0]; x != p; x = fa[x][0])
            if(weight[x] != side[i].w && weight[x] > w)
                w = weight[x];
            for(y = fa[y][0]; y != p; y = fa[y][0])
            if(weight[y] != side[i].w && weight[y] > w)
                w = weight[y];
            det = weight[p] - w;
        }
    }
    printf("%lld\n", det + sum);
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; ++i)
    {
        side[i].u = read(); side[i].v = read(); side[i].w = read();
    }
    ll sum = kru();
    lca();
    solve(sum);
    return 0;
}