比赛 20110730 评测结果 AWAWAWAAAW
题目名称 线段 最终得分 60
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-30 08:59:43
显示代码纯文本
#include <cstdio>
#include <cstring>

const int MAXN=305,MAXM=40005;

struct Node
{
	int v,w;
	Node *next;
	Node (){}
	Node (int _v,int _w,Node *_next):v(_v),w(_w),next(_next){}
	void *operator new(size_t,void *p){return p;}
}*adj[MAXN],pool[MAXM*2],*mem;

inline void addedge(int u,int v,int w)
{
	adj[u]=new (mem++)Node(v,w,adj[u]);
	adj[v]=new (mem++)Node(u,w,adj[v]);
}

bool flag;
int lv[MAXN],belong[MAXN];
int tot;
void dfs(int u)
{
	belong[u]=tot;
	for(Node *p=adj[u];p && flag;p=p->next)
		if (lv[p->v]==-1)
		{
			lv[p->v]=lv[u]^p->w;
			dfs(p->v);
		}
		else if (lv[p->v]!=(lv[u]^p->w))
		{
			flag=false;
			return ;
		}
}

int main()
{
	freopen("line.in","r",stdin);
	freopen("line.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int N,M;
		scanf("%d%d",&N,&M);
		mem=pool;
		flag=true;
		tot=0;
		memset(adj,0,sizeof(adj));
		memset(lv,-1,sizeof(lv));
		memset(belong,-1,sizeof(belong));
		for(int i=0;i<M;i++)
		{
			int u,v,k;
			scanf("%d%d%d",&u,&v,&k);
			if (u!=v)
				addedge(u,v,k);
			else if (k!=0)
				flag=false;
		}
		for(int i=1;i<=N && flag;i++)
			if (lv[i]==-1)
			{
				lv[i]=0;
				tot++;
				dfs(i);
			}
		if (flag) 
			if (belong[1]==belong[N]) 
				printf("%d\n",lv[1]^lv[N]);
			else
				printf("2\n");
		else 
			printf("No Answer\n");
	}
	return 0;
}