NEFU OJ Problem1487 时空乱流题解

时空乱流

  • Problem:E

  • Time Limit:1500ms

  • Memory Limit:65535K

Description

星际飞行员Alice在一次航行中遭遇了时空乱流,时空乱流将导致Alice乘坐的飞船在n个位面之间穿梭。
星际宇航局管理员Bob收到了Alice的求救信号,决定在某些位面上设立监测站,当Alice进入某个已经设立监测站的位面后,她会立即被拯救。
由于不同位面情况不同,设立监测站的花费也不相同。在第i个位面设立监测站,所需花费为
时空乱流已经被星际宇航局完全勘测,每个位面都有通往某个位面的通道,如果第i个位面没有监测站,Alice会前往第个位面。(若Ai=i则会停留在当前位面)
Bob并不知道Alice的初始位置,他必须考虑所有可能的情况,并使用尽可能少的花费,确保能从时空乱流中救出Alice。
你能帮Bob计算出至少要花费多少,才能确保能救出Alice吗?`

Input

第一行一个整数T,表示有T组测试
每组测试数据,第一行一个整数n (1≤n≤200000),表示有n个位面。
第二行n个整数Ci(1≤Ci≤10000),表示在第i个位面设立监测站的花费Ci。
第三行n个整数Ai(1≤Ai≤n),表示第i个位面通往第Ai个位面。

Output

每组数据输出一个整数,表示最小花费。

Sample Input

3
5
1 2 3 2 10
1 3 4 3 3
4
1 10 2 10
2 4 2 2
7
1 1 1 1 1 1 1
2 2 2 3 6 7 6

Sample Output

3
10
2

Hint

输入数据较多,请使用scanf/printf

Source

AotoriChiaki

思路

根据题干,可以建出有向图,例如:

NEFU OJ Problem1487 时空乱流题解

首先分析对于图中所有环,可以缩为一个点,该点的权重等于环上最小权重点

NEFU OJ Problem1487 时空乱流题解NEFU OJ Problem1487 时空乱流题解

然后进行以下分析:

  • 如果不在树根建站,则没有任何节点指向树根,则树根处未收录,必须额外在树根建站,所以树根必建站。
  • 由于每个连通分量中的每个点都会指向树根,如果在树根建站,即可满足该联通分量每个点被收录。

所以在环缩点后每个树的树根建站即可满足题中条件。

如何实现?

对于缩点前的图:

  • 每个点成为树根的条件为入度=0,所以如果有点满足入度为0则可以直接建站。
  • 每个环都会被缩成点,所以针对每个环如果环上的点均满足入度为1(环上的点产生的入度),即可在该环上的最小值点建站

使用并查集完成环的查找和记录

NEFU OJ Problem1487 时空乱流题解NEFU OJ Problem1487 时空乱流题解NEFU OJ Problem1487 时空乱流题解NEFU OJ Problem1487 时空乱流题解

在建图时同时维护一个并查集,如果某边的两端点已经在同一个并查集中(图中红色边),则说明此处有环,只进行记录而不进行并查集合并,可以保证每个环只记录一次。并且这样建成的图是一个树,后续只需要以该边的两端点分别为起点和终点进行dfs即可找到该环的路径。

如下

给TA打赏
共{{data.count}}人
人已打赏
其他

“视界”尽在眼前,海纳视联大模型来了!

2023-11-18 14:34:10

运维笔记

Shell脚本执行超时怎么办?

2023-10-10 17:42:33

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索