D - 图形
题目大意 给定两个无向简单图 F 和 G ，顶点数均为 n 。每次操作可在 F 中删除一条边，或在 F 中无边的一对点间添加一条边。求使 F 满足" 任意 u, v 在 F 中连通当且仅当在 G 中连通 "所需的最小操作数。 t 组数据， \sum n, m_1, m_2 \le 2 \times 10^5 。 思路分…
算法竞赛题解
个人算法竞赛题解博客
标签：# 图论 清除筛选
C - 食物链
题目大意 给定 n 个物种和 m 条能量流动关系（有向边 a_i \to b_i ，能量从 a_i 流向 b_i ），求食物网的 食物链条数 。食物链是从入度为 0 的物种出发、到出度为 0 的物种结束的路径，单独一种孤立生物不算一条食物链。 1 \le n \le 10^5 ， 0 \le m \le 2 \time…
B - 最大生成树
题目大意 有一个 n 个点的完全图，点编号 1 \sim n ，点 (i, j) 之间的边权为 i - j 。求该图最大生成树的边权总和，对 998244353 取模。 2 \le n \le 10^{18} ，且 n 为偶数。 思路分析 完全图的边权只取决于两个端点的距离，直觉上应选"尽量长的边"。用 Kruskal…