博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CF1027D Mouse Hunt 思维
阅读量:5877 次
发布时间:2019-06-19

本文共 3808 字,大约阅读时间需要 12 分钟。

Mouse Hunt
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Medicine faculty of Berland State University has just finished their admission campaign. As usual, about 80%80% of applicants are girls and majority of them are going to live in the university dormitory for the next 44 (hopefully) years.

The dormitory consists of nn rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number ii costs cici burles. Rooms are numbered from 11 to nn.

Mouse doesn't sit in place all the time, it constantly runs. If it is in room ii in second tt then it will run to room aiai in second t+1t+1 without visiting any other rooms inbetween (i=aii=ai means that mouse won't leave room ii). It's second 00 in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.

That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from 11 to nn at second 00.

What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?

Input

The first line contains as single integers nn (1n21051≤n≤2⋅105) — the number of rooms in the dormitory.

The second line contains nn integers c1,c2,,cnc1,c2,…,cn (1ci1041≤ci≤104) — cici is the cost of setting the trap in room number ii.

The third line contains nn integers a1,a2,,ana1,a2,…,an (1ain1≤ai≤n) — aiai is the room the mouse will run to the next second after being in room ii.

Output

Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.

Examples
input
Copy
5 1 2 3 2 10 1 3 4 3 3
output
Copy
3
input
Copy
4 1 10 2 10 2 4 2 2
output
Copy
10
input
Copy
7 1 1 1 1 1 1 1 2 2 2 3 6 7 6
output
Copy
2
Note

In the first example it is enough to set mouse trap in rooms 11 and 44. If mouse starts in room 11 then it gets caught immideately. If mouse starts in any other room then it eventually comes to room 44.

In the second example it is enough to set mouse trap in room 22. If mouse starts in room 22 then it gets caught immideately. If mouse starts in any other room then it runs to room 22 in second 11.

Here are the paths of the mouse from different starts from the third example:

  • 1221→2→2→…;
  • 222→2→…;
  • 3223→2→2→…;
  • 43224→3→2→2→…;
  • 56765→6→7→6→…;
  • 6766→7→6→…;
  • 7677→6→7→…;

So it's enough to set traps in rooms 22 and 66.

 

题意:一个寝室里有n个房间和一个老鼠,老鼠一开始可能在任意一个房间,老鼠会从房间i跳到a[i]房间,问在哪些房间下陷阱可以用最小的代价抓到老鼠?

分析:遍历所有房间,给从这些可能到达的房间打上标记,每次打标志在花费最小的房间布下陷阱

AC代码:

#include #include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ls (r<<1)#define rs (r<<1|1)#define debug(a) cout << #a << " " << a << endlusing namespace std;typedef long long ll;const ll maxn = 1e6+10;const ll mod = 1e9+7;const double pi = acos(-1.0);const double eps = 1e-8;ll n, ans, a[maxn], c[maxn], vis[maxn];int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin >> n; for( ll i = 1; i <= n; i ++ ) { cin >> c[i]; } for( ll i = 1; i <= n; i ++ ) { cin >> a[i]; } for( ll i = 1; i <= n; i ++ ) { ll x = i, v, mn; while( !vis[x] ) { // 找到已被访问过的下一个房间 vis[x] = i, x = a[x]; } if( vis[x] != i ) { continue; } v = x, mn = c[x]; while( a[x] != v ) { //在可能经过的所有房间需要花费最小的房间下陷阱 x = a[x], mn = min( mn, c[x] ); } ans += mn; } cout << ans << endl; return 0;}

  

转载于:https://www.cnblogs.com/l609929321/p/9507607.html

你可能感兴趣的文章
springBoot介绍
查看>>
Intellij IDEA 快捷键整理
查看>>
Redis 通用操作2
查看>>
11. Spring Boot JPA 连接数据库
查看>>
洛谷P2925 [USACO08DEC]干草出售Hay For Sale
查看>>
MapReduce工作原理流程简介
查看>>
那些年追过的......写过的技术博客
查看>>
小米手机解锁bootload教程及常见问题
查看>>
Python内置函数property()使用实例
查看>>
Spring MVC NoClassDefFoundError 问题的解决方法。
查看>>
CentOS 6.9配置网卡IP/网关/DNS命令详细介绍及一些常用网络配置命令(转)
查看>>
python基础教程_学习笔记19:标准库:一些最爱——集合、堆和双端队列
查看>>
C# 解决窗体闪烁
查看>>
CSS魔法堂:Transition就这么好玩
查看>>
【OpenStack】network相关知识学习
查看>>
centos 7下独立的python 2.7环境安装
查看>>
[日常] 算法-单链表的创建
查看>>
前端工程化系列[01]-Bower包管理工具的使用
查看>>
使用 maven 自动将源码打包并发布
查看>>
Spark:求出分组内的TopN
查看>>