BZOJ 1603: [Usaco2008 Oct]打谷机

---

题目

---

1603: [Usaco2008 Oct]打谷机

Time Limit: 5 Sec  Memory Limit: 64 MB

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

Sample Output

1

---

题解

---

这题就是一个DFS，直接搜~这道题目我竟然Ce了一次，总结一下，就是本机编译没有类型重定义，但是到了评测机上就出现了redeclared的错误！说明我们不能作死的起一些华丽的名字的自定义类型，可能会和评测机冲突！

---

代码

---

/*Author:WNJXYK*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define LL long long

inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}

inline void swap(LL &x,LL &y){LL tmp=x;x=y;y=tmp;}

inline int remin(int a,int b){if (a<b) return a;return b;}

inline int remax(int a,int b){if (a>b) return a;return b;}

inline LL remin(LL a,LL b){if (a<b) return a;return b;}

inline LL remax(LL a,LL b){if (a>b) return a;return b;}

struct Linke{

	int u;

	int w;

};

Linke links[1005];

int n;

int dfs(int x,int way){

	if (x==n) return way;

	return dfs(links[x].u,way*(links[x].w==0?1:-1));

}

int main(){

	scanf("%d",&n);

	for (int i=1;i<=n-1;i++){

		int x,y,c;

		scanf("%d%d%d",&x,&y,&c);

		links[x].u=y;

		links[x].w=c;

	}

	printf("%d\n",(dfs(1,1)==1?0:1));

	return 0;

}