# 图论

Acwing395 冗余路径

原题链接:Acwing395

题目描述:为了从 F 个草场中的一个走到另一个,奶牛们有时不得不路过一些她们讨厌的可怕的树。

奶牛们已经厌倦了被迫走某一条路,所以她们想建一些新路,使每一对草场之间都会至少有两条相互分离的路径,这样她们就有多一些选择。

每对草场之间已经有至少一条路径。

给出所有 R 条双向路的描述,每条路连接了两个不同的草场,请计算最少的新建道路的数量,路径由若干道路首尾相连而成。

两条路径相互分离,是指两条路径没有一条重合的道路。

但是,两条分离的路径上可以有一些相同的草场。

对于同一对草场之间,可能已经有两条不同的道路,你也可以在它们之间再建一条道路,作为另一条不同的道路。

……

READ MORE

Acwing256 最大异或和

原题链接:Acwing256

题目描述:给定一个非负整数序列 a,初始长度为 N。

有 M 个操作,有以下两种操作类型:

① ”A x”:添加操作,表示在序列末尾添加一个数 x,序列的长度 N 增大 1。

② ”Q l r x”:询问操作,你需要找到一个位置 p,满足 $l≤p≤r$,使得:a[p] xor a[p+1] xor … xor a[N] xor x 最大,输出这个最大值。

……

READ MORE

Acwing368 银河

原题链接:Acwing368

题目描述:银河中的恒星浩如烟海,但是我们只关注那些最亮的恒星。

我们用一个正整数来表示恒星的亮度,数值越大则恒星就越亮,恒星的亮度最暗是 $1$。

现在对于 $N$ 颗我们关注的恒星,有 $M$ 对亮度之间的相对关系已经判明。

你的任务就是求出这 $N$ 颗恒星的亮度值总和至少有多大。

……

READ MORE

Acwing1175 最大半连通子图

原题链接:Acwing1175

题目描述:一个有向图 $G=(V,E)$ 称为半连通的 (Semi-Connected),如果满足:$∀u,v∈V$,满足 $u→v$ 或 $v→u$,即对于图中任意两点 $u,v$,存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

若 $G′=(V′,E′)$ 满足,$E′$ 是 $E$ 中所有和 $V′$ 有关的边,则称 $G′$ 是 $G$ 的一个导出子图。

若 $G′$ 是 $G$ 的导出子图,且 $G′$ 半连通,则称 $G′$ 为 $G$ 的半连通子图。

若 $G′$ 是 $G$ 所有半连通子图中包含节点数最多的,则称 $G′$ 是 $G$ 的最大半连通子图。

给定一个有向图 $G$,请求出 $G$ 的最大半连通子图拥有的节点数 $K$,以及不同的最大半连通子图的数目 $C$。

由于 $C$ 可能比较大,仅要求输出 $C$ 对 $X$ 的余数。

……

READ MORE

Recents
Categories
Tags
Links