首页 > 代码库 > bzoj1603[Usaco2008 Oct]打谷机*
bzoj1603[Usaco2008 Oct]打谷机*
bzoj1603[Usaco2008 Oct]打谷机
题意：
给个树，每个边都有边权0和1。0表示两个端点同色，1表示两个端点不同色。点1为黑色，问点n哪种颜色（颜色只有两种：黑和白）。树大小≤1000。
题解：
dfs一发。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 1010 7 using namespace std; 8 9 inline int read(){10 char ch=getchar(); int f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 int g[maxn][maxn],n,ans[maxn];16 void dfs(int x,int fa){17 inc(i,1,n)if(i!=fa&&g[x][i]!=-1)ans[i]=ans[x]^g[x][i],dfs(i,x);18 }19 int main(){20 n=read(); memset(g,-1,sizeof(g)); inc(i,1,n-1){int x=read(),y=read(),z=read(); g[x][y]=g[y][x]=z;}21 dfs(1,0); printf("%d",ans[n]); return 0;22 }
20160917
bzoj1603[Usaco2008 Oct]打谷机*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。