【CF603E】 Pastoral Oddities


CF 传送门:CF603E

整体二分 + 可撤销并查集。

(这个方法是个人认为较简单的,除外还有LCT 维护线段树分治的做法。)

考场上苦想正解觉得自己写得出来的我真的太 naive 了

Solution

Part 1 每个点的度数均为奇数

不妨称度数为奇数的点为奇点,为偶数称偶点。

逐一考虑题目限制条件。显然先从“每个点为奇点”考虑,因为它相对特殊。

先扔出一个很重要的结论:一个连通图内所有点为奇点,等价于该连通图内有偶数个节点。证明如下:

  • 必要性:考场上阿巴出“若某连通图内的每个点都为奇点,则该图中点数必定为奇数”。

    这个性质的证明不难,手玩小样例即可,形象地说,奇点必定是成双成对出现的,若想要一个偶点变为奇点,必须同时让另一个偶点变为奇点(或者重新构造出一个点)。自己画画图构造一下很容易就能得出。

  • 充分性:对于一个有偶数个节点的连通图,我们可以在它任意一种形态的生成树上构造出“所有点为奇点”的局面。

    具体地,从底向上遍历每一个节点,如果这个节点儿子连上来的边数为偶数,就连上他与父亲的边,反之则不然。对于根节点,因为其子树内其他节点的度数之和为 奇数 x 奇数 = 奇数,而度数总和为偶数,所以根节点的度数也为奇数。

结合这个结论和其充分性证明中的构造方式,可以发现:对于一个连通图,只要添上某一条边之后,它的点数变为偶数,那这条边就是这个边集中的最大边权。进一步地,想要把这个图真真切切构造成一个“所有点都为奇点”的情况,需要在图中删边,但是删的边一定不会是这条最大权的边。

由此,明白:既然我们只是要求“最小化边集中的最大边权”,那这个连通图内部如何删边我们其实毫不关心,只需要明白有这个操作,但是代码实现中无需写出,要想找到“最小化边集中的最大边权”,只需要看在加入哪条边之后总点数变为偶数即可。直白地说,对合法的边,能加就加。

Part 2 最小化边集中的最大边权

然后来考虑“最小化边集中的最大边权”这个限制条件。条件反射肯定就想到二分答案的做法,但是本题是动态加边,复杂度不允许每次加边后都来一次二分,故引导我们去考虑整体二分的做法。进一步地,为了保证能够使用整体二分,考虑证明最终答案的单调性。这个通过观察样例输出简单思考发现答案一定是单调不下降的。

按照整体二分的套路来,函数 solve(ql, qr, vl, vr) 表示现在处理在 /([ql,qr]/) 之间的询问,且它们的答案都是边按照权值从小到大排序之后,位于 /([vl,vr]/) 之中的某边的边权。(使用 /(e/) 数组按输入顺序存放边,/(b/) 数组按权值从小到大存放边。)

按照之前的推论,我们根本不关心连通块内部怎么删边,故要先确保在 /(e/) 中编号小于 /(ql/)、/(w/) 中编号小于 /(vl/) 的边都先加入。为了继续二分处理询问,设 /(mid=/frac{vl+vr}{2}/),我们就需要求出在询问 /([ql,qr]/),中,哪个询问的答案是 /(b_{mid}.w/),记此答案为 /(Ans/)。若求出了 /(Ans/),那么接下来要递归的两个函数的分别是 solve(ql, Ans - 1, mid + 1, vr)solve(Ans, qr, vl, mid),即分别递归左子区间和右子区间。

Part 3 加边

再回过头考虑加边细节:

  1. 为求解 /(Ans/) 加边:我们首先肯定要保证 /(e/) 中编号小于 /(ql/) 的边且 /(w/) 中编号小于 /(mid/) 的边都必须得加入,这是根据能加就加的原则。然后再从 /(e_{ql}/) 遍历到 /(e_{qr}/),依次加入这些边,直到加入某条边之后整个图中没有一个内部点数为奇数的连通块,则这条边就是 /(Ans/)。
  2. 为递归 solve(ql, Ans - 1, mid + 1, vr) 加边:显然,为了不妨碍下一个递归函数,我们只需要在递归这个函数之前加入 /(e/) 中编号小于 /(ql/) 的边且 /(w/) 中编号小于 /(mid/) 的边。
  3. 为递归 solve(Ans, qr, vl, mid) 加边:同理,此时要先加入 /(e/) 中编号在 /([ql, Ans)/) 的边且其边权小于 /(b_{vl}.w/) 的边。

综上,我们可以发现:

  1. 我们想维护连通块内的节点数;
  2. 每次递归函数中,上述三个加边步骤有所重复(比如第一步的前半部分和第二步);
  3. 我们想尽可能节省空间。

这三条(或者更多)指向了我们维护这些边、连通块所使用的工具:可撤销并查集。

为什么要“可撤销”?发现第一步加边之后,要想执行第二步加边操作,只需要撤销掉第一步后半部分的加边操作即可,无需重新加边(显然,撤销比初始化再重新加边要方便的多)。

嗯,然后这道题就结束了。

简单提一嘴可撤销并查集,它其实就是在并查集的基础上,不路径压缩,然后再开个栈存放每次合并的两个根节点,便于撤销即可。

Code

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 3e5 + 5;
int n, m, num;
int fa[maxn], sz[maxn], stk[maxn], tot, ans[maxn];
struct node{
    int u, v, w, id;
}e[maxn], b[maxn];
bool operator <(const node &a, const node &b){
    return a.w < b.w;
}
 
inline int fnd(int x){
    return x == fa[x] ? x : fnd(fa[x]);
}
 
inline void erase(int lmt){
    while(tot > lmt){
        int v = stk[tot--], u = fa[v];
        fa[v] = v, sz[u] -= sz[v];
        if((sz[u] & 1) and (sz[v] & 1)) num += 2; 
    }
}
 
inline void merge(int x, int y){
    x = fnd(x), y = fnd(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    if((sz[x] & 1) and (sz[y] & 1)) num -= 2;
    sz[x] += sz[y], fa[y] = x, stk[++tot] = y;
}
 
inline void slv(int ql, int qr, int vl, int vr){
    if(ql > qr or vr < vl) return;
    if(vl == vr){
        rep(i, ql, qr) ans[i] = b[vl].w; return;
    } int mid = vl + vr >> 1, nw = tot;
    rep(i, vl, mid) if(b[i].id < ql) merge(b[i].u, b[i].v);//加入之前的边 
    int Ans = qr + 1, nw2 = tot;
    rep(i, ql, qr){
        if(e[i].w <= b[mid].w) merge(e[i].u, e[i].v);
        if(!num){Ans = i; break;}//找到 ans[mid] 
    } erase(nw2), slv(ql, Ans - 1, mid + 1, vr), erase(nw);//递归左子区间 
    rep(i, ql, Ans - 1) if(e[i].w <= b[vl].w) merge(e[i].u, e[i].v);//添加满足限制的边 
    slv(Ans, qr, vl, mid), erase(nw); //递归右子区间 
} 
 
int main(){
    scanf("%d%d", &n, &m), num = n;
    rep(i, 1, n) sz[i] = 1, fa[i] = i;
    rep(i, 1, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), e[i].id = i, b[i] = e[i];
    sort(b + 1, b + m + 1), b[m + 1].w = -1;
    slv(1, m, 1, m + 1); rep(i, 1, m) printf("%d/n", ans[i]);
    return 0;
}

感谢阅读。

原创文章,作者:wdmbts,如若转载,请注明出处:https://blog.ytso.com/276408.html

(0)
上一篇 2022年7月23日
下一篇 2022年7月23日

相关推荐

发表回复

登录后才能评论