描述 Description
Farmer John 有一个过时的打谷机（收割小麦），它需要带子来带动。发动机驱动轮 1 总是顺时针旋转的，用来带动转轮 2，转轮 2 来带动转轮 3，等等。一共有 n（2<=n<=1000）个转轮（n-1 条带子）。上面的图解描述了转轮的两种连接方式，第一种方式使得两个轮子旋转的方向相同，第二种则相反。 给出一串带子的信息： Si—驱动轮 Di—被动轮 *Ci—连接的类型（0 = 直接连接，1 = 交叉连接） 不幸的是，列出的信息是随即的。 作为样例，考虑上面的图解，n=4，转轮 1 是驱动轮，可以得知最后转轮 4 是逆时针旋转的。
输入格式 InputFormat
第一行：一个数 n * 第二行到第 n 行：每一行有三个被空格隔开的数：Si，Di，Ci
输出格式 OutputFormat
第一行：一个单独的数，表示第 n 个转轮的方向，0 表示顺时针，1 表示逆时针。
样例输入 SampleInput
20
9 10 0
7 8 1
2 3 0
14 15 1
11 12 1
13 14 0
19 20 0
5 6 0
16 17 0
1 2 1
3 4 1
4 5 1
12 13 1
18 19 0
8 9 1
17 18 1
6 7 1
15 16 1
10 11 1
样例输出 SampleOutput
0
来源 Source
资格赛
代码 Code
dfs, 异或.
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct wheel
{
int to,next,val;
}a[2001];
int head[2001];
int f[2001];
int b[2001];
int i,j,t,n,m,l,r,k,z,y,x;
void ins(int u,int v,int w)
{
a[++m].to=v;a[m].val=w;a[m].next=head[u];
head[u]=m;
}
void dfs(int s)
{
int i,j,t;
b[s]=true;
if (s==n) return ;
for (i=head[s];i;i=a[i].next)
{
f[a[i].to]=f[s]^a[i].val;
if (b[a[i].to]==false) dfs(a[i].to);
if (b[n]==true) return ;
}
}
int main()
{
memset(b,0,sizeof(b));
scanf("%d",&n);
m=0;
for (i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
ins(x,y,z);ins(y,x,z);
}
f[1]=0;
dfs(1);
printf("%dn",f[n]);
return 0;
}