Portals

题目描述

Bessie 位于一个由 $N$（$2\le N\le 10^5$）个顶点组成的网络中，顶点标号为 $1\ldots N$，以及 $2N$ 个传送门，传送门标号为 $1\ldots 2N$。每个传送门连接两个不同的顶点 $u$ 和 $v$（$u\neq v$）。多个传送门可能连接同一对顶点。 每个顶点 $v$ 与四个互不相同的传送门相邻。与 $v$ 相邻的传送门列表为 $p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]$。 你当前所在的位置可以表示为一个有序对 $(\text{当前顶点}, \text{当前传送门})$；即形如 $(v,p_{v,i})$ 的一对，其中 $1\le v \le N$ 且 $1\le i\le 4$。你可以使用以下任意一种操作来改变当前位置： 通过当前传送门移动，从而改变当前顶点。 切换当前传送门。在每个顶点处，列表中的前两个传送门配成一对，而后两个传送门也配成一对。也就是说，如果你当前位置是 $(v,p_{v,2})$，你可以切换为使用传送门 $(v,p_{v,1})$，反之亦然。类似地，如果你当前位置是 $(v,p_{v,3})$，你可以切换为使用传送门 $(v,p_{v,4})$，反之亦然。不允许其他切换（例如，你不能从传送门 $p_{v,2}$ 切换到传送门 $p_{v,4}$）。 总共有 $4N$ 个不同的位置。不幸的是，未必能通过一系列操作从任意一个位置到达任意另一个位置。因此，你可以花费 $c_v$（$1\le c_v\le 1000$）个 moonies，将与顶点 $v$ 相邻的传送门列表按任意顺序重新排列。重新排列后，列表中的前两个传送门配成一对，后两个传送门也配成一对。 例如，如果你将与顶点 $v$ 相邻的传送门按顺序排列为 $[p_{v,3},p_{v,1},p_{v,2},p_{v,4}]$，这意味着当你在顶点 $v$ 时， 如果你当前在传送门 $p_{v,1}$，你可以切换为使用传送门 $p_{v,3}$，反之亦然。 如果你当前在传送门 $p_{v,2}$，你可以切换为使用传送门 $p_{v,4}$，反之亦然。 你将不再能从传送门 $p_{v,1}$ 切换到 $p_{v,2}$，或从传送门 $p_{v,3}$ 切换到传送门 $p_{v,4}$，反之亦然。 请计算为了修改网络使得可以从任意位置到达任意其他位置，所需的最小 moonies 总数。保证测试数据的构造方式使得至少存在一种有效的修改网络的方法。

输入格式

第一行包含 $N$。 接下来的 $N$ 行每行描述一个顶点。第 $v+1$ 行包含五个用空格分隔的整数 $c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}$。 保证对每个 $v$，$p_{v,1},p_{v,2},p_{v,3},p_{v,4}$ 两两不同，并且每个传送门恰好出现在两个顶点的邻接列表中。

输出格式

输出一行，包含为了修改网络使得可以从任意位置到达任意其他位置所需的最小 moonies 总数。

5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5

13

提示

只需对顶点 $1$ 和 $4$ 的邻接列表进行重新排列。这总共需要 $c_1+c_4=13$ 个 moonies。我们可以令 $p_1=[1,9,4,8]$ 且 $p_4=[7,4,6,3]$。 SCORING: 在测试点 2-4 中，对所有 $v$ 有 $c_v=1$。 测试点 5-12 不满足额外限制。 题目鸣谢：Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold