#P6313. 「JOISC 2016 Day 3」电报

    ID: 5802 传统题 200ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高+/省选-功能图入度剥离基环树拆环补集转化

「JOISC 2016 Day 3」电报

题目描述

题目译自 JOISC 2016 Day3 T3 「電報」

给出 NN 个点,每个点的出度均为 11,给出这 NN 个点初始指向的点 AiA_i,和改变这个点指向的目标所需要的价值 CiC_i。
求让所有点强连通的最小花费。

输入格式

第一行输入一个数 NN 表示点的个数。
之后的 NN 行每行两个数 AiA_i CiC_i 表示第 ii 个点指向第 AiA_i 个点,更改该点指向的点花费为 CiC_i。

输出格式

共一行,为让所有点强连通的最小花费。

4
2 2
1 4
1 3
3 1
4
4
2 2
1 6
1 3
3 1
5
4
2 2
1 3
4 2
3 3
4
3
2 1
3 1
1 1
0

数据范围与提示

对于全部的数据,1≤N≤1051 \leq N \leq 10^{5} ,1≤Ai≤N1 \leq A_i \leq N , Ai≠iA_i \neq i , 1≤Ci≤1091 \leq C_i \leq 10^{9} 。

具体子任务限制及得分情况如下表:

Subtask 限制 分数
11 1≤N≤101 \leq N \leq 10 1010
22 1≤N≤151 \leq N \leq 15 3030
33 1≤N≤30001 \leq N \leq 3000
44 无追加限制