[BJWC2010]严格次小生成树

ゝ一纸荒年。 2021-10-24 04:12 258阅读 0赞

题面 [洛谷P4180][P4180]

## 题目描述 ##

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

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

## 输入输出格式 ##

**输入格式：**

第一行包含两个整数N 和M，表示无向图的点数与边数。 接下来 M行，每行 3个数x y z 表示，点 x 和点y之间有一条边，边的权值为z。

**输出格式：**

包含一行，仅一个数，表示严格次小生成树的边权和。(数据保证必定存在严格次小生成树)

## 输入输出样例 ##

**输入样例\#1：**

5 6
    1 2 1 
    1 3 2 
    2 4 3 
    3 5 4 
    3 4 3 
    4 5 6

## 说明 ##

数据中无向图无自环； 50% 的数据N≤2 000 M≤3 000； 80% 的数据N≤50 000 M≤100 000； 100% 的数据N≤100 000 M≤300 000 ，边权值非负且不超过 10^9 。

解析：

容易联想到严格次小生成树应该由最小生成树转化而来

那么问题就转化为一只一个图的最小生成树，如何求它的次小生成树

我们可以考虑枚举每一条非树边，把它加入MST中，再删去这条边的两端点在MST中的简单路径上的最长边，由MST的性质，这条边一定不大于我们要加的边（如果大于，那将他删去，再加上新的边，依然是一棵树，并且新树的边权和比原树的小，这与MST的定义矛盾），但又要考虑到生成树必须严格最小，那么我们删去的这条边必须小于新加的边，即两边权值不能相等

由于我的倍增不太熟练，我采用树链剖分+线段树的方法维护路径的最大值与严格次大值

在线段树的向上更新过程中，更新最大值和普通的一样，严格次大值的更新就是先取两儿子的严格次大值的max，如果两儿子的最大值不等，再取该点的值与两儿子的最大值的max，这部分代码如下

![1626119-20190711211314224-721232774.png][]

线段树查询过程中的区间合并的操作与这部分类似，详见下面的完整代码

树链剖分的边权转点权后，求路径的最大值与次大值，注意到lca的边权是不能取的，我右边的大导演wys就这样wa了几个点

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 100005, maxm = 300005;
    const ll inf = 1e16;
    
    template<class T> void read(T &re)
    {
        re=0;
        T sign=1;
        char tmp;
        while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1;
        re=tmp-'0';
        while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0');
        re*=sign;
    }
    
    int n, m;
    ll sum, ans;
    struct edge{
        int u, v;
        ll val;
    }e[maxm];
    
    vector<pair<int, ll> > G[maxn], H[maxn];
    
    bool cmp(edge x, edge y)
    {
        return x.val < y.val;
    }
    
    int f[maxn];
    
    int Find(int x)
    {
        return x == f[x]? x: f[x] = Find(f[x]);
    }
    
    int cnt, dep[maxn], son[maxn], size[maxn], fa[maxn], top[maxn], pos[maxn];
    ll a[maxn], v[maxn];
    
    void dfs1(int x)
    {
        size[x] = 1;
        for(unsigned int i = 0; i < G[x].size(); ++i)
        {
            int id = G[x][i].first;
            if(fa[x] == id)        continue ;
            fa[id] = x;
            v[id] = G[x][i].second;
            dep[id] = dep[x] + 1;
            dfs1(id);
            if(size[id] > size[son[x]])
                son[x] = id;
            size[x] += size[id];
        }
    }
    
    void dfs2(int x)
    {
        a[++cnt] = v[x];
        pos[x] = cnt;
        if(son[fa[x]] == x)
            top[x] = top[fa[x]];
        else
            top[x] = x;
        if(son[x])
            dfs2(son[x]);
        for(unsigned int i = 0; i < G[x].size(); ++i)
        {
            int id = G[x][i].first;
            if(fa[x] == id || id == son[x])        continue ;
            dfs2(id);
        }
    }
    
    struct pr{
        ll mx, mx2;
    };
    
    int tot, root;
    struct seg_tree{
        int l, r, ls, rs;
        pr p;
    }tr[maxn<<1];
    
    void update(int x)
    {
        tr[x].p.mx = max(tr[tr[x].ls].p.mx, tr[tr[x].rs].p.mx);
        tr[x].p.mx2 = max(tr[tr[x].ls].p.mx2, tr[tr[x].rs].p.mx2);
        if(tr[tr[x].ls].p.mx != tr[tr[x].rs].p.mx)
            tr[x].p.mx2 = max(tr[x].p.mx2, min(tr[tr[x].ls].p.mx, tr[tr[x].rs].p.mx));
    }
    
    void build(int &x, int l, int r)
    {
        if(l == r)
        {
            x = l;
            tr[x].l = tr[x].r = l;
            tr[x].p.mx = a[l];
            tr[x].p.mx2 = -inf;
            return ;
        }
        x = ++tot;
        tr[x].l = l;
        tr[x].r = r;
        int mid = (l + r)>>1;
        build(tr[x].ls, l, mid);
        build(tr[x].rs, mid + 1, r);
        update(x);
    }
    
    pr get_max(pr x, pr y)
    {
        pr ret;
        ret.mx = max(x.mx, y.mx);
        ret.mx2 = max(x.mx2, y.mx2);
        if(x.mx != y.mx)
            ret.mx2 = max(ret.mx2, min(x.mx, y.mx));
        return ret;
    }
    
    pr query(int x, int l, int r)
    {
        if(l <= tr[x].l && tr[x].r <= r)
        {
            return tr[x].p;
        }    
        pr ret = (pr){-inf, -inf};
        int mid = (tr[x].l + tr[x].r)>>1;
        if(l <= mid)
            ret = get_max(ret, query(tr[x].ls, l, r));
        if(mid < r)
            ret = get_max(ret, query(tr[x].rs, l, r));
        return ret;
    }
    
    void work(int x, int y, ll val)
    {
        pr t = (pr){-inf, -inf};
        while(top[x] != top[y])
        {
            if(dep[top[x]] > dep[top[y]])
            {
                t = get_max(t, query(root, pos[top[x]], pos[x]));
                x = fa[top[x]];
            }
            else
            {
                t = get_max(t, query(root, pos[top[y]], pos[y]));
                y = fa[top[y]];
            }
        }
        if(dep[x] < dep[y])
            t = get_max(t, query(root, pos[x]+1, pos[y]));
        else if(dep[y] < dep[x])
            t = get_max(t, query(root, pos[y]+1, pos[x]));
        ll z = (val != t.mx? t.mx : t.mx2);
        ans = min(ans, sum - z + val);
    }
    
    int main()
    {    
        read(n);read(m);
        for(int i = 1; i <= m; ++i)
            read(e[i].u), read(e[i].v), read(e[i].val);
        sort(e + 1, e + m + 1, cmp);
        for(int i = 1; i <= n ; ++i)
            f[i] = i;
        for(int i = 1; i <= m ; ++i)
        {
            int p = Find(e[i].u), q = Find(e[i].v);
            if(p != q)
            {
                sum += e[i].val;
                G[e[i].u].push_back(make_pair(e[i].v, e[i].val));
                G[e[i].v].push_back(make_pair(e[i].u, e[i].val));
                f[p] = q;
            }
            else
                H[e[i].u].push_back(make_pair(e[i].v, e[i].val));
        }
        dfs1(1);
        dfs2(1);
        tot = n;
        build(root, 1, n);
        ans = inf;
        for(int i = 1; i <= n; ++i)
            for(unsigned int j = 0; j < H[i].size(); ++j)
                work(i, H[i][j].first, H[i][j].second);
        printf("%lld", ans);
        return 0;
    }

2019-07-11

转载于:https://www.cnblogs.com/Joker-Yza/p/11172460.html

[P4180]: https://www.luogu.org/problemnew/show/P4180
[1626119-20190711211314224-721232774.png]: /images/20211023/1950d879ac5241549d9c2eec9c96cbd1.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/1d8574e4a879442caeb3486bb33a216a.png