当前位置: 代码迷 >> 综合 >> 【usaco 2013 feb Bronze】信息传递
  详细解决方案

【usaco 2013 feb Bronze】信息传递

热度:36   发布时间:2023-10-09 12:41:12.0
题目:



   农夫约翰的奶牛通常是按1到N进行编号的,奶牛们相互之间有一种特殊的信息传输方式。在信息传递的过程中,每只奶牛的信息最多传递到另一只奶牛,对于奶牛i,Fi表示他要传递信息的那只奶牛的编号,这里i和Fi肯定是不同的,如果Fi是0,则表示奶牛i没有要传递信息给其他的奶牛。



   不幸的是,奶牛们知道了这种传递信息的方式可能会导致一个死循环。如果一个奶牛传递信息最终会导致一个死循环,那么我们就说这只奶牛在死循环里面。



问题描述:



请帮助奶牛们计算有多少头奶牛没有在死循环里面。

题解:

最后不指向0的牛都死了。

代码:

vara,b:array[1..10000] of longint;f:array[0..10000] of boolean;n,i,j,l:longint;
beginassign(input,'relay.in');reset(input);assign(output,'relay.out');rewrite(output);readln(n);for i:=1 to n doreadln(a[i]);fillchar(b,sizeof(b),0);for i:=1 to n dobeginj:=i;fillchar(f,sizeof(f),false);while j>0 dobeginif f[j] thenbeginf[0]:=true;break;end;f[j]:=true;j:=a[j];end;if f[0] thenfor j:=1 to n doif f[j] then b[j]:=1;end;for i:=1 to n doif b[i]=0 then inc(l);writeln(l);close(input);close(output);
end.

  相关解决方案