电报

NC53241. 电报

描述

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

给出N个点，每个点的出度均为1，给出这N个点初始指向的点 $A_i$ ，和改变这个点指向的目标所需要的价值 $C_i$ 。
求让所有点强连通的最小花费。

输入描述

第一行输入一个数N表示点的个数。
之后的N行每行两个数表示第i个点指向第个点，更改该点指向的点花费为。

输出描述

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

示例1

输入:

输出:

说明:

很显然，把 $2 \rightarrow1$ 的这条边改成 $2 \rightarrow4$ （花费4）的情况下构成强连通分量花费最小。

示例2

输入:

输出:

说明:

很显然把 $1 \rightarrow2$ 的这条边改成 $1 \rightarrow4$ 花费2，把 $3 \rightarrow1$ 的这条边改成 $3 \rightarrow2$ 花费3的情况下构成强连通分量花费最小，总花费为5。

示例3

输入:

输出:

示例4

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

详情