首页 > 其他分享 >紫丁香 题解

紫丁香 题解

时间:2023-11-06 20:35:36浏览次数:39  
标签:return int 题解 rx ry tot fa 紫丁香

紫丁香 题解

前言

来自一场 \(\text{noip}\) 提高模拟赛的题目。

题目描述

有 \(n\) 点 \(m\) 边的 简单无向连通图,点编号为 \(0\sim n-1\),要求删掉若干条边,最大化奇数度点的个数。

求:能得到最大答案的构造,用 \(m\) 长的 \(01\) 串表示,\(1\) 表示保留该边,\(0\) 表示不保留,输出字典序最大的方案。

思路

建树

首先,我们可以在图中建出一棵树。

由于最后要输出字典序最大,所以我们要尽可能地删后面的边。

所以可以用按秩(按秩序)并查集建出一棵树。注意,为什么要按秩?因为我们可以通过节点度数大小按秩建树,这样有利于树的深度不会太深。

code

int find(int x) {
    // note:不能使用路径压缩
    return fa[x] == x ? x : find(fa[x]);
}

bool merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return 0;
    if (d[rx] > d[ry])
        swap(rx, ry);
    Fa[++tot] = { rx, ry };
    d[ry] += d[rx];
    fa[rx] = ry;
    return 1;
}

signed main() {
    for (int i = m; i >= 1; i--)
        chose[i] = merge(E[i].ft, E[i].sd);
}

遍历边

然后一条一条边遍历,如果非树边,直接记录一下该边不用删,然后从自己已知爬到祖先,让每个度 ++。所以之前为什么要按秩并查集建树呢?——就是因为这里 \(fa_i\) 必须记录自己的父亲,不可以压缩路径记录祖先,时间复杂度会 \(\text{T}\),所以要是树的深度尽可能小。

code

void change(int x) {
    while (x) {
        d[x]++;
        if (x == fa[x])
            break;
        x = fa[x];
    }
}

signed main() {
    for (int i = 1; i <= m; i++) {
        if (chose[i] == 0) {
            ans[i] = 1;
            change(E[i].ft), change(E[i].sd);
        }
    }
}

这是为了将那些之前没有增加进树的度的点更新度的状态 \(^{[*]}\) (注释见结尾)。

如果遍历到了树边 \((u,v)\in E\),考虑要不要保留。如果要保留,那把之前不连通时,各自的祖先 \((root_u,root_v)\) 拿出来,断边。

再看这俩祖先的度有没有成为奇数。

如果任意一个是奇数,那就可以保留 \((u,v)\) 该边,并且做更新度状态的操作(同上)。否则没有必要保留,先前断掉的 \((root_u,root_v)\) 也不需要再次建边。

code

bool split(int x, int y) {
    int rx = Fa[tot].ft, ry = Fa[tot].sd;
    tot--;
    d[ry] -= d[rx];
    fa[rx] = rx;
    if ((d[rx] & 1) || (d[ry] & 1)) {
        change(x);
        change(y);
        return 1;
    }
    return 0;
}

signed main() {
    for (int i = 1; i <= m; i++) {
        if (chose[i])
            ans[i] = split(E[i].ft, E[i].sd);
    }
}

通过一系列操作,就可以得到哪些边要删,哪些边不用删了。

完整代码

code

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

#define int long long
#define pii pair<int, int>
#define ft first
#define sd second

const int MAXN = 6e5 + 5, MAXM = 9e5 + 5;

int n, m;
int tot;
int fa[MAXN], d[MAXN];
pair<int, int> E[MAXM], Fa[MAXM];
bool ans[MAXM], chose[MAXM];

int find(int x) {
    // note:不能使用路径压缩
    return fa[x] == x ? x : find(fa[x]);
}

bool merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return 0;
    if (d[rx] > d[ry])
        swap(rx, ry);
    Fa[++tot] = { rx, ry };
    d[ry] += d[rx];
    fa[rx] = ry;
    return 1;
}

void change(int x) {
    while (x) {
        d[x]++;
        if (x == fa[x])
            break;
        x = fa[x];
    }
}

bool split(int x, int y) {
    int rx = Fa[tot].ft, ry = Fa[tot].sd;
    tot--;
    d[ry] -= d[rx];
    fa[rx] = rx;
    if ((d[rx] & 1) || (d[ry] & 1)) {
        change(x);
        change(y);
        return 1;
    }
    return 0;
}

signed main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++) fa[i] = i, d[i] = 1;
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%lld%lld", &u, &v);
        u++, v++;
        E[i] = { u, v };
    }
    for (int i = m; i >= 1; i--) chose[i] = merge(E[i].ft, E[i].sd);
    for (int i = 1; i <= m; i++) {
        if (chose[i])
            ans[i] = split(E[i].ft, E[i].sd);
        else {
            ans[i] = 1;
            change(E[i].ft), change(E[i].sd);
        }
    }
    for (int i = 1; i <= m; i++) putchar(ans[i] ? '1' : '0');
    return 0;
}

结尾

\(^{[*]}\):个人认为最难点在于 change 函数。为什么要从 \(u\to root_u\) 的路径上所有点都要度 ++?一说,为了该边路径上每个点的奇偶性(好像不太对)。

现在我还没找到最准确的答案,现在属于似懂非懂。如果你想到了,欢迎评论交流。

标签:return,int,题解,rx,ry,tot,fa,紫丁香
From: https://www.cnblogs.com/wang-holmes/p/17813634.html

相关文章

  • 完蛋!大模型解密(LLM Riddles) 题解
    https://intsensing.cn/llmgame/index第一章T1:输出括号里的内容,不输出括号本身和其余附加内容.(1+1=3)T2:讲故事T3:猫T4:啊T5:啊1T6:有一个字,左边是反犬旁,右边是句,请重复这个字五遍第二章T1:请输出11个0T2:142857T3:10010010T4:输出十一万四千五百一十四的阿拉伯数字形式,不要输......
  • [ARC105C] Camels and Bridge 题解
    题意给定\(N\)个重物,其中第\(i\)个重物的重量为\(w_i\)。现在要将其排成一排,可以任意指定相邻两个重物的距离。同时给定\(M\)个限制,其中第\(i\)个限制为\((l_i,v_i)\),表示要求不存在长度为\(l_i\)的线段,使得其包括的重物重量之和大于\(v_i\)。最小化重物间的最大......
  • [ARC105D] Let's Play Nim 题解
    题意给定\(N\)个背包,其中第\(i\)个背包中有\(a_i\)个石子。同时还有\(N\)个盘子,初始时盘子中没有石子。两人轮流执行下列操作:若存在背包中还有石子,选择一个非空背包和盘子,将背包中的石子放入盘子中,注意这里对盘子没有要求;若不存在背包中还有石子,选择一个非空盘子,将盘......
  • 题解 LOJ3483【[USACO21FEB] Counting Graphs P】
    题解P7418【[USACO21FEB]CountingGraphsP】problemBessie有一个连通无向图\(G\)。\(G\)有\(N\)个编号为\(1\ldotsN\)的结点,以及\(M\)条边(\(1\leN\le10^2,N-1\leM\le\frac{N^2+N}{2}\))。\(G\)有可能包含自环(一个结点连到自身的边),但不包含重边(连接同一对结点......
  • Daleks' Invasion 题解
    Daleks'Invasion题目大意给定一张无向带权图,对于每条边求一个最大的\(x\),使得将这条边的边权修改为\(x\)后这条边能位于这张图的最小生成树上。思路分析没事干了就把之前写过的题拉出来水题解。我们先把原图的最小生成树求出来,考虑每条边\((u,v)\),分类讨论:如果这条边......
  • Groceries in Meteor Town 题解
    GroceriesinMeteorTown题目大意维护一颗带权树,支持以下操作:将\([l,r]\)内的点变为白色。将\([l,r]\)内的点变为黑色。查询点\(x\)到任意一个白色节点的简单路径上的最大值。思路分析没事干了把以前的题拿出来写题解。看到『简单路径上的最大值』的字样首......
  • Harvester 题解
    Harvester题目大意给定\(n\timesm\)的网格,每次可以选一行或一列,将这一行或一列上的数全部取走,最多可以取四次,问取走的数的和的最大值。思路分析没事干了把以前写过的题拿出来写题解。分类讨论题。在只能取四次的情况下一共只有这么几种可能:选四行:毫无疑问,行之间互不......
  • 大文件上传 问题解决三种方案
    最近遇见一个需要上传百兆大文件的需求,调研了七牛和腾讯云的切片分段上传功能,因此在此整理前端大文件上传相关功能的实现。在某些业务中,大文件上传是一个比较重要的交互场景,如上传入库比较大的Excel表格数据、上传影音文件等。如果文件体积比较大,或者网络条件不好时,上传的时间会......
  • vue视频直接播放rtsp流;vue视频延迟问题解决;webRTC占cpu太大卡死问题解决;解决webRTC播
    vue视频直接播放rtsp流;vue视频延迟问题解决;webRTC占cpu太大卡死问题解决;解决webRTC播放卡花屏问题::https://blog.csdn.net/killerdoubie/article/details/133884070......
  • 【洛谷 P1046】[NOIP2005 普及组] 陶陶摘苹果 题解(比较)
    [NOIP2005普及组]陶陶摘苹果题目描述陶陶家的院子里有一棵苹果树,每到秋天树上就会结出个苹果。苹果成熟的时候,陶陶就会跑去摘苹果。陶陶有个厘米高的板凳,当她不能直接用手摘到苹果的时候,就会踩到板凳上再试试。现在已知个苹果到地面的高度,以及陶陶把手伸直的时候能够达到的......