首页 > 代码库 > BZOJ1603: [Usaco2008 Oct]打谷机
BZOJ1603: [Usaco2008 Oct]打谷机
1603: [Usaco2008 Oct]打谷机
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 602 Solved: 458
[Submit][Status]
Description
Farmer John有一个过时的打谷机(收割小麦),它需要带子来带动。发动机驱动轮1总是顺时针旋转的,用来带动转轮2,转轮2来带动转轮3,等等。一共有n(2<=n<=1000)个转轮(n-1条带子)。上面的图解描述了转轮的两种连接方式,第一种方式使得两个轮子旋转的方向相同,第二种则相反。 给出一串带子的信息: *Si—驱动轮 *Di—被动轮 *Ci—连接的类型(0=直接连接,1=交叉连接) 不幸的是,列出的信息是随即的。 作为样例,考虑上面的图解,n=4,转轮1是驱动轮,可以得知最后转轮4是逆时针旋转的。
Input
*第一行:一个数n *第二行到第n行:每一行有三个被空格隔开的数:Si,Di,Ci
Output
*第一行:一个单独的数,表示第n个转轮的方向,0表示顺时针,1表示逆时针。
Sample Input
4
2 3 0
3 4 1
1 2 0
2 3 0
3 4 1
1 2 0
Sample Output
1
HINT
Source
资格赛
题解:
太水了。。。一遍dfs
代码:
1 const maxn=1500; 2 var f:array[0..maxn,0..maxn] of longint; 3 g:array[0..maxn] of longint; 4 v:array[0..maxn] of boolean; 5 i,n,x,y,z:longint; 6 procedure dfs(x:longint); 7 var i:longint; 8 begin 9 v[x]:=true;10 for i:=1 to n do11 if (f[x,i]<>0) and (not(v[i])) then12 begin13 if f[x,i]=1 then g[i]:=g[x] else g[i]:=g[x] xor 1;14 dfs(i);15 end;16 end;17 begin18 assign(input,‘input.txt‘);assign(output,‘output.txt‘);19 reset(input);rewrite(output);20 readln(n);21 for i:=1 to n-1 do22 begin23 readln(x,y,z);inc(z);24 f[x,y]:=z;25 f[y,x]:=z;26 end;27 g[1]:=0;28 dfs(1);29 writeln(g[n]);30 close(input);close(output);31 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。