1900E

题意 给你一张有向图，点有点权，现进行以下操作直到无法进行： 选择两条首尾相连的边 \((a,b)\) 和 \((b,c)\) 且 \(a\) 与 \(c\) 间没边，添加边 \((a,c)\)。 求操作完后图中最长的 不经过重复点的路径，并求这种路径中经过的点的点权和最小值。 思路 先考虑 DAG ......

题意 给你一张有向图，点有点权，现进行以下操作直到无法进行： 选择两条首尾相连的边 \((a,b)\) 和 \((b,c)\) 且 \(a\) 与 \(c\) 间没边，添加边 \((a,c)\)。 求操作完后图中最长的 不经过重复点的路径，并求这种路径中经过的点的点权和最小值。 思路 先考虑 DAG ......

考虑题目的限制条件：存在 $a\to b, b\to c$ 的边，就会有 $a\to c$ 的边。 考虑 $p_{1\sim k}$，满足这 $k$ 个点按顺序组成了一个环且无重点。 那么 $p_1\to p_2, p_2\to p_3$，就有 $p_1\to p_3$，又有 $p_3\to p_4 ......

题目传送门 前置芝士：缩点、拓扑排序。 题目描述 有向图 \(G\) 有 \(N\) 个点，\(M\) 条边，点 \(u\) 的点权为 \(A_u\)。 若存在三元组 \(a,b,c\) 使得 \(a\) 至 \(b\) 有一条边，\(b\) 至 \(c\) 有一条边，则连一条 \(a\) 至 \( ......