ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

8278: Portals

内存限制：128 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：10 通过：7
提交提交记录统计Web Board

题目描述

Bessie 位于一个由  Bessie 位于一个由 NN 个编号为 1\dots N1…N 的结点以及 2N2N 个编号为 1\cdots 2N1⋯2N 的传送门所组成的网络中。每个传送门连接两个不同的结点 uu 和 vv（u≠vu=v）。可能有多个传送门连接同一对结点。
每个结点 vv 与四个不同的传送门相连。与 vv 相连的传送门列表由 p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]pv=[pv,1,pv,2,pv,3,pv,4] 给出。


你的当前位置可以用有序对（当前结点，当前传送门）表示；即一个有序对 (v,p_{v,i})(v,pv,i) ，其中 1\le v\le N1≤v≤N 以及 1\le i\le 41≤i≤4。你可以使用以下任一操作来改变你的当前位置：
    1. 由穿过当前传送门来改变当前结点。
    1. 改变当前传送门。在每一个结点上，列表的前两个传送门是配对的，后两个传送门也是配对的。也就是说，如果你的当前位置是 (v,p_{v,2})(v,pv,2)，你可以转而使用传送门 (v,p_{v,1})(v,pv,1)，反之亦然。类似地，如果你的当前位置是 (v,p_{v,3})(v,pv,3)，你可以转而使用传送门 (v,p_{v,4})(v,pv,4)，反之亦然。没有其他改变传送门的方式（例如，你不能从传送门 p_{v,2}pv,2 转去传送门 p_{v,4}pv,4 ）。
总共有 4N4N 个不同的位置。不幸的是，并不一定每一个位置都可以从另外的每一个位置经过一系列操作而到达。所以，以 c_vcv 哞尼的代价，你可以以任意顺序重新排列与 vv 相邻的传送门列表。在此之后，列表中的前两个传送门互相配对，同时后两个传送门也互相配对。
例如，如果你将与 vv 相邻的传送门以 [p_{v,3},p_{v,1},p_{v,2},p_{v,4}][pv,3,pv,1,pv,2,pv,4] 的顺序重新排列，这意味着如果你位于结点 vv ，


  • 如果你当前位于传送门 p_{v,1}pv,1 ，你可以转而使用传送门 p_{v,3}pv,3，反之亦然。

  • 如果你当前位于传送门 p_{v,2}pv,2 ，你可以转而使用传送门 p_{v,4}pv,4，反之亦然。 你不再能够从传送门 p_{v,1}pv,1 转至传送门 p_{v,2}pv,2，或从传送门 p_{v,3}pv,3 转至 p_{v,4}pv,4 ，反之亦然。
计算修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。输入保证存在至少一种修改网络的合法方式。

输入格式

输入的第一行包含 NN。
以下 NN 行每行描述一个结点。第 v+1v+1 行包含五个空格分隔的整数 c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}cv,pv,1,pv,2,pv,3,pv,4。


输入保证对于每一个 vv ，p_{v,1},p_{v,2},p_{v,3},p_{v,4}pv,1,pv,2,pv,3,pv,4 各不相同，且每个传送门出现在恰好两个结点的邻接表中。

输出格式

输出一行，包含修改这一网络使得每一个位置都可以从另外的每一个位置到达所需要花费的哞尼的最小数量。


2≤N≤105，1≤cv≤103。

输入格式

The first line contains N.

The next N lines each describe a vertex. Line v+1v+1 contains five space-separated integers cv,pv,1,pv,2,pv,3,pv,4.

It is guaranteed that for each v pv,1,pv,2,pv,3,pv,4 are all distinct, and that every portal appears in the adjacency lists of exactly two vertices.

输出格式

A single line containing the minimum total amount of moonies required to modify the network in order to make it possible to reach every possible location from every other location.

输入样例 复制 

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

数据范围与提示

It suffices to permute the adjacency lists of vertices 1 and 4. This requires a total of c1+c4=13 moonies. We can let p1=[1,9,4,8] and p4=[7,4,6,3].

SCORING:

  • In test cases 2-4, cv=1 for all v.
  • Test cases 5-12 satisfy no additional constraints.

分类标签