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

CXY07 · 2019-06-12 18:36:50 · 题解

被这题的INF值给弄自闭了

很气

题目链接：P4180 【模板】严格次小生成树[BJWC2010]

看了 Julao 们的题解，表示做法都很强 只是我不会 ，但是我的做法是 Kruskal + 树剖，这个做法的好像只有一位巨佬写了题解 然而我没看懂 ，所以自己来写一篇

至于为什么写树剖。。。是某 zxyhymzg 巨佬哄骗我做的。。。

首先强烈申明，此题的 INF 应该开大些，我就因为没开大就 90WA 了无数遍

我这边开的是 2147483647 * 10^6，可把我坑死了

进入正题

首先可以证明：至少有一个严格次小生成树和最小生成树只有一条边的差异 只是我不会证

所以首先就可以先跑 Kruskal ，求出最小生成树(mst)，再枚举没有在 mst 中的边，进行更新即可

听着很简单对吧

但是此处这个更新的过程就很有意思了。当我们现在枚举一条边 e[i] ，它没有在 mst 之中：如何将其加入，有保证它有可能是一个严格次小生成树呢？

我们把 e[i] 这条边所连的两个点分别叫做 x 和 y 好了，那么此时x，y都肯定在 mst 之中被一条或多条在mst中的边给连接起来。当我们需要加入e[i]时，一定需要删除x，y的连线上的某一条边才可以保证加入新边之后还是一棵树。

删哪一条呢？

请注意标题：严格次小生成树，那么我们需要找到这条路径上边权最大的那个点，删除它，这样才能保证新的生成树与 mst 的边权和的差最小，也就是有可能成为次小生成树（ps：此时新加入边的边权肯定会比mst中连接x，y的连线中任意一条边的边权都要大，否则它也将进入mst）。

再注意两个字：严格，也就是说，新的生成树和mst的边权差不能相等！ 那么从这个条件中，我们可以得到什么？——其实就是x，y之间的路径上那个边权最大的边的边权和e[i]的边权不能相等！！！

所以，我们不仅要维护两点之间的最大值，还要维护两点之间的严格次大值

那树剖的算法就很明朗啦，先跑Kruskal，把mst在树剖算法中连边，接着枚举所有没有在mst中的边，更新即可。哦对了，树剖维护边权的话，还是要把边化为点做的

以下代码会先分为几块来讲解

首先是代码的变量申明

#define pii pair<long long,long long>
#define INF 2147483647000000

const long long MAXN = 4e5 + 10;
const long long MAXM = 3e5 + 10;

long long n,m,mst,smst;
//mst 最小生成树的边权和，smst 严格次小生成树的边权和
long long ufs[MAXN],nodecnt,ww[MAXN];
//ufs 并查集 nodecnt，点数(之后会加)，ww点权
long long head[MAXN],edgesize;
//建图用
long long dep[MAXN],son[MAXN],fa[MAXN],siz[MAXN];
long long id[MAXN],top[MAXN],w[MAXN],nodesize;
//树剖套餐

和三个结构体

struct EDGE_For_Kru {
    long long x,y,w;
    bool select;
    bool operator < (const EDGE_For_Kru &b) const {return w < b.w;}
} G[MAXM << 1];//最小生成树用的

struct EDGE {
    long long nxt;
    long long to;
} edge[MAXM << 2];//树剖用的

struct SegmentTree {
    long long val1;//最大值
    long long val2;//严格次大值
} seg[MAXN << 2];//线段树

最水的部分Kruskal

就是简单的跑了，没什么好说的。

long long find(long long x) {
    if(ufs[x] != x) ufs[x] = find(ufs[x]);
    return ufs[x]; 
}

void unity(long long x,long long y) {
    if(find(x) != find(y)) 
        ufs[find(y)] = find(x);
}

inline long long Kruskal() {
    nodecnt = n;//首先把点的个数设为 n
    sort(G + 1,G + m + 1);
    long long cnt = 0,res = 0;
    for(long long i = 1;i <= n; ++i)
        ufs[i] = i;
    for(long long i = 1;i <= m; ++i) {
        long long x = G[i].x,y = G[i].y;
        if(find(x) == find(y)) continue;
        unity(x,y); G[i].select = true;
        addedge(x,++nodecnt); addedge(nodecnt,x);//加入树剖的边
        addedge(y,nodecnt); addedge(nodecnt,y);//同上
        ww[nodecnt] = G[i].w;//新点的权值就是边权
        cnt++, res += G[i].w;
        if(cnt == n - 1) break;
    }
    return res;
}

接着就是树剖部分啦

其实大部分就是树剖常规打法，两个DFS直接就是裸的，只不过线段树方面稍微要注意，在更新两个 val 值的时候略微有一点麻烦，这个在代码中详细讲。

以下的 pii 均指 pair<longlong,long long> ,第一个值表示最大值，第二个表示严格次大值，有不少函数以 pii 为返回值。

void DFS1(long long now,long long f,long long deep) {
    dep[now] = deep;
    fa[now] = f;
    siz[now] = 1;
    long long maxson = -1;
    for(long long i = head[now];i;i = edge[i].nxt) {
        if(edge[i].to == f) continue;
        DFS1(edge[i].to,now,deep + 1);
        siz[now] += siz[edge[i].to];
        if(siz[edge[i].to] > maxson) {
            maxson = siz[edge[i].to];
            son[now] = edge[i].to;
        }
    }
}//最平凡的DFS1

void DFS2(long long now,long long topf) {
    id[now] = ++nodesize;
    top[now] = topf;
    w[nodesize] = ww[now];
    if(!son[now]) return;
    DFS2(son[now],topf);
    for(long long i = head[now];i;i = edge[i].nxt) {
        if(edge[i].to == son[now] || edge[i].to == fa[now]) continue;
        DFS2(edge[i].to,edge[i].to);
    }
}//最平凡的DFS2

pii getval(pii v1,pii v2) {//从下面四个值中间找出最大值和严格次大值
    long long res1,res2,t = 3;
    long long v11 = v1.first,v12 = v1.second;
    long long v21 = v2.first,v22 = v2.second;
    long long vv[5] = {0,v11,v12,v21,v22};
    sort(vv + 1,vv + 5);//给这四个值排序
    res1 = vv[4];//最大值
    while(vv[t] == vv[4]) t--;//严格次大值
    res2 = vv[t];
    return make_pair(res1,res2);//返回pii
}

void build(long long root,long long l,long long r) {
    if(l == r) {
        seg[root].val1 = w[l];
        seg[root].val2 = 0;
        return;
    }
    long long mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    pii q = make_pair(seg[root << 1].val1,seg[root << 1].val2);
    pii p = make_pair(seg[root << 1 | 1].val1,seg[root << 1 | 1].val2);//两棵子树的分别两个值
    pii res = getval(p,q); //更新本节点的值
    seg[root].val1 = res.first,seg[root].val2 = res.second;
}

pii query(long long root,long long l,long long r,long long L,long long R) {
    if(L <= l && r <= R) return make_pair(seg[root].val1,seg[root].val2);
    long long mid = (l + r) >> 1;
    pii res;
    if(L <= mid) res = getval(res,query(root << 1,l,mid,L,R));
    if(R > mid) res = getval(res,query(root << 1 | 1,mid + 1,r,L,R));
    //同样是更新
    return res;
}

pii QUERY(long long x,long long y) {
    pii res;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res = getval(res,query(1,1,nodesize,id[top[x]],id[x]));//也是一样更新
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    pii g = query(1,1,nodesize,id[x],id[y]);
    res = getval(res,g);
    return res;
}

所有 getval 的用法类似于普通线段树中的 max 函数，用来更新 val 值，把它这样理解即可

以上代码建议仔细阅读，这是整个代码中最关键部分的实现

再说主函数

其实就是一些平常的输入啊之类的，接着就是上方代码思路描述部分的代码实现了

    read(n); read(m);//自己写的龟速读
    for(long long i = 1;i <= m; ++i) {
        read(G[i].x); 
        read(G[i].y); 
        read(G[i].w);//输入Kruskal的边
    }
    mst = Kruskal();//mst的边权和
    smst = INF;//次小生成树的边权和，初始化成 INF
    DFS1(1,0,1); DFS2(1,1);//树剖
    build(1,1,nodesize);//树剖
    for(long long i = 1;i <= m; ++i) {
        if(G[i].select) continue;//如果这条边在mst中，就不能选
        long long wn = G[i].w;//加入的新边的边权
        pii tmp = QUERY(G[i].x,G[i].y);//树剖找出两点之间的最大和严格次大边权
        if(tmp.first != wn) smst = min(smst,mst - tmp.first + wn);
        //如果最大值和新边权不相等，就用最大值直接更新
        else smst = min(smst,mst - tmp.second + wn);
        //否则说明如果去掉最大值再加入新边权后，边权和将不会变化，不满足"严格次小"的规定，则需要用严格次大值更新
    }
    cout << smst << endl;//输出即可

最后的代码（蒟蒻不知道为什么，这个代码不开O2就 0 分了 那就开着吧）

//Code By CXY
#include<bits/stdc++.h>
using namespace std;

#define pii pair<long long,long long>
#define INF 2147483647000000

const long long MAXN = 4e5 + 10;
const long long MAXM = 3e5 + 10;

struct EDGE_For_Kru {
    long long x,y,w;
    bool select;
    bool operator < (const EDGE_For_Kru &b) const {return w < b.w;}
} G[MAXM << 1];

struct EDGE {
    long long nxt;
    long long to;
} edge[MAXM << 2];

struct SegmentTree {
    long long val1;
    long long val2;
} seg[MAXN << 2];

long long n,m,mst,smst;
long long ufs[MAXN],nodecnt,ww[MAXN];
long long head[MAXN],edgesize;
long long dep[MAXN],son[MAXN],fa[MAXN],siz[MAXN];
long long id[MAXN],top[MAXN],w[MAXN],nodesize;

template <typename T> inline void read(T &a) {
    a = 0;char c = getchar();long long f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') {a = (a << 3) + (a << 1) + (c ^ 48);c = getchar();}
    a *= f;
}

inline void addedge(long long x,long long y) {
    edge[++edgesize].nxt = head[x];
    edge[edgesize].to = y;
    head[x] = edgesize;
}
//-----------------------------------------------------------------------
long long find(long long x) {
    if(ufs[x] != x) ufs[x] = find(ufs[x]);
    return ufs[x]; 
}

void unity(long long x,long long y) {
    if(find(x) != find(y)) 
        ufs[find(y)] = find(x);
}

inline long long Kruskal() {
    nodecnt = n;
    sort(G + 1,G + m + 1);
    long long cnt = 0,res = 0;
    for(long long i = 1;i <= n; ++i)
        ufs[i] = i;
    for(long long i = 1;i <= m; ++i) {
        long long x = G[i].x,y = G[i].y;
        if(find(x) == find(y)) continue;
        unity(x,y); G[i].select = true;
        addedge(x,++nodecnt); addedge(nodecnt,x);
        addedge(y,nodecnt); addedge(nodecnt,y);
        ww[nodecnt] = G[i].w;
        cnt++, res += G[i].w;
        if(cnt == n - 1) break;
    }
    return res;
}
//-----------------------------------------------------------------------
void DFS1(long long now,long long f,long long deep) {
    dep[now] = deep;
    fa[now] = f;
    siz[now] = 1;
    long long maxson = -1;
    for(long long i = head[now];i;i = edge[i].nxt) {
        if(edge[i].to == f) continue;
        DFS1(edge[i].to,now,deep + 1);
        siz[now] += siz[edge[i].to];
        if(siz[edge[i].to] > maxson) {
            maxson = siz[edge[i].to];
            son[now] = edge[i].to;
        }
    }
}

void DFS2(long long now,long long topf) {
    id[now] = ++nodesize;
    top[now] = topf;
    w[nodesize] = ww[now];
    if(!son[now]) return;
    DFS2(son[now],topf);
    for(long long i = head[now];i;i = edge[i].nxt) {
        if(edge[i].to == son[now] || edge[i].to == fa[now]) continue;
        DFS2(edge[i].to,edge[i].to);
    }
}

pii getval(pii v1,pii v2) {
    long long res1,res2,t = 3;
    long long v11 = v1.first,v12 = v1.second;
    long long v21 = v2.first,v22 = v2.second;
    long long vv[5] = {0,v11,v12,v21,v22};
    sort(vv + 1,vv + 5);
    res1 = vv[4];
    while(vv[t] == vv[4]) t--;
    res2 = vv[t];
    return make_pair(res1,res2);
}

void build(long long root,long long l,long long r) {
    if(l == r) {
        seg[root].val1 = w[l];
        seg[root].val2 = 0;
        return;
    }
    long long mid = (l + r) >> 1;
    build(root << 1,l,mid);
    build(root << 1 | 1,mid + 1,r);
    pii q = make_pair(seg[root << 1].val1,seg[root << 1].val2);
    pii p = make_pair(seg[root << 1 | 1].val1,seg[root << 1 | 1].val2);
    pii res = getval(p,q); seg[root].val1 = res.first,seg[root].val2 = res.second;
}

pii query(long long root,long long l,long long r,long long L,long long R) {
    if(L <= l && r <= R) return make_pair(seg[root].val1,seg[root].val2);
    long long mid = (l + r) >> 1;
    pii res;
    if(L <= mid) res = getval(res,query(root << 1,l,mid,L,R));
    if(R > mid) res = getval(res,query(root << 1 | 1,mid + 1,r,L,R));
    return res;
}

pii QUERY(long long x,long long y) {
    pii res;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        res = getval(res,query(1,1,nodesize,id[top[x]],id[x]));
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    pii g = query(1,1,nodesize,id[x],id[y]);
    res = getval(res,g);
    return res;
}

//-----------------------------------------------------------------------

int main () {
    read(n); read(m);
    for(long long i = 1;i <= m; ++i) {
        read(G[i].x); 
        read(G[i].y); 
        read(G[i].w);
    }
    mst = Kruskal();
    smst = INF;
    DFS1(1,0,1); DFS2(1,1);
    build(1,1,nodesize);
    for(long long i = 1;i <= m; ++i) {
        if(G[i].select) continue;
        long long wn = G[i].w;
        pii tmp = QUERY(G[i].x,G[i].y);
        if(tmp.first != wn) smst = min(smst,mst - tmp.first + wn);
        else smst = min(smst,mst - tmp.second + wn);
    }
    cout << smst << endl;
    return 0;//华丽丽地结束
}

到这里就结束了，本代码中最有趣的部分应该就是那个 getval 函数和它对应的更新了 虽然把我调到自闭，大家可以 自行品味 多多研读

初二的 OIer ，请多关照