P2661-信息传递

深藏阁楼爱情的钟 2023-06-01 08:54 10阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define pb push_back
     6 typedef long long ll;
     7 using namespace std;
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 
    24 int e[200003];
    25 int state[200003];
    26 int m[200003];
    27 int vis[200003];
    28 int st;
    29 int N;
    30 int rnt = 0x3f3f3f3f;
    31 void dfs(int nw)
    32 {
    33     if(vis[nw])
    34         return ;
    35     vis[nw] = 1;
    36     if(state[e[nw]]==-1)
    37     {
    38         rnt = min(rnt,m[nw]-m[e[nw]]+1);
    39         return ;
    40     }
    41     state[nw] = -1;
    42     m[e[nw]] = m[nw]+1;
    43     dfs(e[nw]);
    44     state[nw] = 0;
    45 }
    46 int main()
    47 {
    48 //    freopen("testdata.txt","w+",stdin);
    49     N = read();
    50     _for(i,1,N+1)
    51         e[i] = read();
    52     _for(i,1,N+1)
    53     {
    54         if(!vis[i])
    55             dfs(i);
    56     }
    57     write(rnt);
    58     return 0;
    59 }

转载于:https://www.cnblogs.com/Asurudo/p/11504209.html

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 LCP 07. 传递信息

小朋友 A 在和 ta 的小伙伴们玩传信息游戏，游戏规则如下：有 n 名玩家，所有玩家编号分别为 0 ～ n-1，其中小朋友 A 的编号为 0 每个玩家都有固定的若干个

水深无声/ 2023年10月04日 16:28/ 0 赞/ 50 阅读

相关 P2661-信息传递

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

深藏阁楼爱情的钟/ 2023年06月01日 08:54/ 0 赞/ 11 阅读

相关小程序模板传递信息

<import src="../productList/productList.wxml"></import> <!--

╰+攻爆jí腚メ/ 2023年01月12日 14:57/ 0 赞/ 187 阅读

相关 P2661 [NOIP2015 提高组] 信息传递

P2661 \[NOIP2015 提高组\] 信息传递——有向图相关算法⭐️⭐️⭐️⭐️ 题目描述有 n个同学（编号为 1到 n）正在玩一个信息传递的游戏。在游戏里

柔光的暖阳◎/ 2022年10月27日 02:23/ 0 赞/ 198 阅读

相关 c++：与&, &p, 指针传递，引用传递，数组形参

\与& 先理解地址和数据，想象内存里面是一个个的小盒子，每个盒子对应一个编号，这个编号就是地址，盒子里存放的就是数据。 &是取地址运算符，如有 int a; 即有一个小

女爷i/ 2022年10月13日 02:00/ 0 赞/ 239 阅读

相关 LCP 07. 传递信息

2021-07-01 LeetCode每日一题链接：[https://leetcode-cn.com/problems/chuan-di-xin-xi/][https_

曾经终败给现在/ 2022年10月12日 00:45/ 0 赞/ 165 阅读

相关 P2661 信息传递

题目描述有n个同学（编号为1到n）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为i的同学的信息传递对象是编号为Ti同学。游戏开始时，

悠悠/ 2022年05月26日 01:26/ 0 赞/ 196 阅读

相关洛谷 P2661 信息传递（NOIP 提高 2015）

[传送门][Link 1] 本题本来是一个很好的并查集的题（似乎靠的就是并查集），然而蒟蒻我刚刚学习了 tarjan 所以就用 terjan做了一下大概题意

电玩女神/ 2021年11月16日 06:42/ 0 赞/ 275 阅读

相关 P2512 [HAOI2008]糖果传递

题目描述有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。输入输出格式输入格式：小朋友个数n

港控/mmm°/ 2021年09月30日 07:04/ 0 赞/ 347 阅读

相关题解 P2512 [HAOI2008]糖果传递

首先我们要用到一些[均分纸牌][Link 1]的思想(已经理解这种思想的大佬请跳过): 设\\(A\_i\\)表示第\\(i\\)个小朋友原有的糖果数量, 设\\(ave\

小鱼儿/ 2021年09月29日 11:56/ 0 赞/ 277 阅读